작심 24/7

5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면 www.acmicpc.net 내가 지금 시뮬레이션을 구현하고 있는 건지 노가다를 하고 있는 건지 잠시 현타(?) 왔던 문제이다. 그림처럼 한 면을 돌리면 그 면과 인접한 옆 면들도 돌려지기 때문에 돌리는 면과 옆 면 이 두 가지 경우로 나누어서 계산해주어야 한다. 돌리는 면에 따라 돌려져야 하는 칸들을 시계 방향으로 전개도에 표시해보았다. 1. 윗 면 (U) 2. 아랫 면 (D) 3. 앞 면 (F) 4. 뒷 면 (B) 5. 왼쪽 면 (L) 6. 오른쪽 면 (R) 기본 형태 : 1 → 2 → 3 ..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net BFS를 이용하여 상어 크기와 같은 물고기가 있거나 빈칸인 공간으로 이동하면서 상어 크기보다 작은 물고기를 발견하면 우선순위 큐에 BFS의 깊이(걸린 시간), x좌표, y좌표를 넣어준다. 탐색을 다 마치고 돌아와 우선순위 큐가 비어있으면 먹을 수 있는 물고기가 없는 것이므로 종료 후 최종 시간 출력, 비어있지 않으면 큐 안에서 1. 깊이(걸린 시간)가 가장 작은 순서대로 2. x좌표가 가장 위에 있는 순서대로 3. y좌표가 가장 왼쪽에 있는 순서대로 오..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 블록을 옮기는 방향에 따라 다르게 검사하며 1. 위로 옮길 때 -> 각 열 위에서부터 검사 2. 아래로 옮길 때 -> 각 열 아래에서부터 검사 3. 왼쪽으로 옮길 때 -> 각 행 왼쪽에서부터 검사 4. 오른쪽으로 옮길 때 -> 각 행 오른쪽에서부터 검사 같은 숫자가 연속해서 나오면 (빈칸 무시) 그 두 숫자를 더한 값을 큐에 넣고 같은 숫자가 연속하지 않을 때는 그 숫자만 큐에 넣는다. 한 줄의 검사가 끝나면 큐에 있는 숫자를 보드판에..

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최소 점수를 구하는 과정을 예로 들자면 현재의 첫 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값) + 현재의 첫 번째 칸의 숫자 이다. 현재의 두 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값 or 이전의 세 번째 칸의 최솟값) + 현재의 두 번째 칸의 숫자 이다. 현재의 세 번째 칸의 최솟값은 그림에 나와있는 대로 min(이전의 두 번째 칸의 최솟..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ▷다른 방식 풀이 보러가기 상, 하, 좌, 우 방향으로 굴리면서 DFS 한다. 빨간 구슬과 파란 구슬이 일직선 상에 있을 경우 order 함수를 통해서 어느 구슬 먼저 굴려야 할지 판단해준 뒤 그 순서에 따라서 다음 경우에 맞게 처리해준다. 1. 빨간 구슬이 구멍에 들어가건 안 들어가건 상관없이 파란 구슬이 구멍 안으로 들어가는 경우 -> 실패이므로 구슬들의 위치만 원 상태로 복귀 후 다음 방향으로 넘어감(cont..

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 프로그래머스 지형 이동과 비슷한 문제이다. 1. BFS로 섬의 번호를 매겨준다. 2. 섬과 섬 사이의 거리의 최솟값을 그래프에 저장한다. 1) 가로 방향 다리 모든 행을 검사하면서 A섬 끝→B섬 시작 일 때가 다리를 놓는 경우이므로 파란색 화살표일 경우에만 그래프에 저장한다. 이때 거리는 1보다 커야 하고 A섬→B섬에 이미 거리가 저장되어 있으면 그 거리와 현재 거리를 비교하여 더 작은 값을 넣어준다. 2) 세로 방향 다리 모든 열을 검사하는..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 완전 탐색, DP 두 가지 방법으로 풀 수 있다. 완전 탐색은 1일부터 차근차근 가능한 날을 모두 골라 최댓값을 구해주면 되고 DP는 i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 최대 이익, i 일을 선택하지 않을 때 얻는 최대 이익) → i 일에 얻는 이익 = max(i 일을 선택할 때 얻는 이익 + i+T[i]일에 얻는 최대 이익, i+1일에 얻는 최대 이익) → DP[i] = max(P[i] + DP[i + T[i]], DP[i + 1]) 라는 점화식을 세워주고 재귀로 구현하면 된다. 1. 완전 탐색 #include #include using namespace std; int N, M..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다. 그러므로 두 선거구로 나눌 수 없는 경우는 연결되어 있는 그룹이 세 개 이상일 때이므로 이 경우를 가려주기 위해 먼저 BFS로 연결된 그룹이 몇 개인지 세어준다. 3개 이상일 경우 -> -1 출력 2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력 1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감 두 선거구로 나누는 방법은 N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구..