목록전체 글 (117)
풀이 보관함
🔗 문제 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 제한 1 ≤ N, M ≤ 10 3 ≤ N×M ≤ 100 2 ≤ 섬의 개수 ≤ 6 ✏️ 풀이 ✍️ 문제 정리 다리를 설치해서 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자. [변수] NxM 맵 바다 0 땅 1 [다리 설치 조건] 다리는 바다에만 건설할 수 있다. 다리의 방향은 한 방향이다 다리의 길이는 2 이상이다. 다리의 양끝은 인접한 바다 위에 있어야 한다. (섬과 닿는 부분은 길이로 치지 않는다)..
🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ✏️ 풀이 실수한게 많아서 시간을 들여 풀이를 써보고자 한다. 문제 내용 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다. 이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고, 그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라 비용(cost ) : (i*i) + (i-1) * (i-1) // i가 범위일 때 수익(profit) : 범위 내의 집의 수(cnt) * M 손해를 보지 않으려면 아래 조건을 만족해야 한다. cost -..
🔗 문제 17069번: 파이프 옮기기 2 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net ✏️ 풀이 맨 처음 맵에 파이프가 가로로 있다. 끝점이 (0, 1) 파이프가 있을 수 있는 상태 : type {가로, 세로, 대각선} 각 타입에 따라 옮길 수 있는 조건이 있다. 문제를 잘 읽고 예제도 잘 보자. 문제를 잘 안 읽으면 예제 5번이 이해가 안 갈 수 있다. 아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어..
🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. ✏️ 풀이 먼저 문제 정리 부터 한다. [맵이 가질 수 있는 상태] EMPTY : ..
🔗 문제 2636번: 치즈 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net N, M ≤ 100 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게..
🔗 문제 2467번: 용액 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net ✏️ 풀이 문제에서 보아야 할 것은 이미 용액이 "정렬된 상태 "인 것이다. 더 해야 할 용액도 2개다 싶어서 투포인터를 떠올렸다. 양 끝을 start, end라는 변수로 가리키며 그 합을 sum에 저장해 주었다. 이때 값은 오름차순 정렬이므로 start는 가장 작은 값(0 위치), end는 가장 큰 값 (N-1 위치)을 가리킨다. 만약 sum이 0이라면 더 이상 진행할 필요가 없다. 만약 sum < 0 이라면 작은 값을 가리키는..
🔗 문제 21609번: 상어 중학교 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 🖍 풀이 6달전에 푼거보다 개선되어서 다시 올리는 풀이 ✌🏻 문제를 읽고 코드 흐름을 간단하게 정리해보자. while(flag) { //1. 블럭 그룹들 찾기 //2. 조건에 맞는 블럭 제거하고 점수 얻기 // => 블럭 없으면 종료 flag = false //3. 아래로 중력 작용 //4. 반 시계 방향으로 회전 //4. 아래로 중력 작용 } 조건 정리 ✔️ 맵의 상태는 3가지의 블럭 종류와 빈 칸으로 이루어진다. enum..
🔗 문제 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net ✏️ 풀이 일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다. 이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서. 총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다. 풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다.. 문제를 읽으면 알겠지만, 간단하..
🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=582 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai ✏️ 풀이 다익스트라 문제다. (1) 출발 지점이 주어져있고, (2) 양방향이며, (3) 가중치가 양수다. 무엇보다 출발 지점에서 특정지점까지 필요한 값을 출력해야한다는게 다익스트라문제라는 큰 힌트다. 다익스트라를 학습할 때 주로 사용하는 최소 경로가 아니라 최소 레벨을 구해야하는게 작은 차이일 뿐이다. 정석 다익스트라 풀이로 priority_queue를 이용했다. dp[node]에 1에서 node까지 가는 가장 큰 레벨을 저장한다. 문제의 제약조건을 보면 총 노드의 수는 $2 ≤ N ≤ 10,000$ 로 한정되어 있다. 가..
🔗 문제 11404번: 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ✍️ 풀이 제목부터 거처주는 플로이드 기초 문제 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 플로이드 와샬이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 그렇다면 A→B 중 가장 작은 비용 값을 저장하자. 💾 소스 #include #include #include const int INF = 1e9; std::vector adj; int N..