본문 바로가기

Programming

BOJ 16985 · Maaaaaaaaaze 알고리즘 분류 : BFS, 브루트 포스 3차원 미로를 탈출하는 것을 구현해야 한다. 단순한 3차원 BFS는, BOJ 7569번 '토마토'처럼 구현하면 된다. 하지만, 이 문제는 각 층의 미로가 회전하고, 각 층마다 섞여서 까다롭다. 미로를 제대로 만드는 것이 중요하다. 미로 맵을 나타낼 3차원 배열의 인덱스는 [층 번호] [X좌표] [Y좌표] 이다.각 층을 섞는 것을 순열을 통해 만든다. 별도의 인덱스[0~4]를 만들어서 층을 나타내고, 이를 순열로 섞으면 된다.층을 섞은 후, 각 층을 회전해야 한다. 별도의 회전 함수를 만들고, 5중 for문 또는 재귀를 통해 각 층을 순차적으로 회전시킨다.첫 층의 출발 칸(0, 0, 0)이 이동할 수 있는 칸[1]인 경우에만 다음 층을 섞는다. 이동할 수 없는 칸[0..
BOJ 1149 · RGB거리 알고리즘 분류 : 다이나믹 프로그래밍 RGB 거리의 각 집에 색칠하는 비용을 구해야 한다. DP로 구현하여 색칠할 때 드는 최소 비용을 구하면 된다. D[N][M] : N번째 집을 M으로 칠할 때 드는 최소 비용 (M은 색깔 0~2)D[N][0] : N번째 집을 빨간색(0)으로 칠할 때 드는 최소 비용D[N][1] : N번째 집을 초록색(1)으로 칠할 때 드는 최소 비용D[N][2] : N번째 집을 파란색(2)으로 칠할 때 드는 최소 비용D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = P[1][2] C++ 소스코드 #include #include using namespace std; int n, d[1001][3], p[1001][3]; void solve() { f..
BOJ 1012 · 유기농 배추 알고리즘 분류 : DFS 배추 밭에 놓아야 하는 배추흰지렁이의 마릿수를 구해야 한다. 배추흰지렁이는 하나의 배추 그룹에 한 마리만 놓으면, 최소 마릿수가 된다. 즉, 이 문제는 배추 그룹의 수를 세는 플러드 필 문제이다. 배추가 인접한 상하좌우로 연결되면, 이것은 하나의 배추 그룹이 된다. 우선 N*M 사이즈의 배열 A를 만들고 모든 좌표를 0으로 둔다.입력으로 주어지는 배추의 좌표 (X, Y)를 배열 A에 1로 둔다.N*M 사이즈의 맵을 DFS를 통해 모든 곳을 방문할 때까지 완전 탐색한다.DFS로 다음 좌표를 이동할 때, 배추(1)로만 이동한다.테스트케이스가 여러 개 주어지므로, 초기화가 매번 필요하다. C++ 소스코드 #include #include int m, n, k, ans; int a[51]..
BOJ 17070 · 파이프 옮기기 1 알고리즘 분류 : 백트래킹 파이프를 옮겨서 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구해야 한다. 파이프는 2칸을 차지하지만, 파이프의 끝만 고려하면 된다. 파이프의 상태는 3가지로 나눌 수 있다. 1. 가로로 놓여있는 상태 (0) : 가로(0) → 가로(0) 또는 대각선(2)2. 세로로 놓여있는 상태 (1) : 세로(1) → 세로(1) 또는 대각선(2)3. 대각선으로 놓여있는 상태 (2) : 대각선(2) → 가로(0) 또는 세로(1) 또는 대각선(2)가로(0)에서 세로(1)로 곧바로 이동할 수 없고, 세로(1)에서 가로(0)로 곧바로 이동할 수 없다. 재귀 함수의 인자는 (X 좌표, Y 좌표, 파이프 상태) 이다.현재 파이프 상태에 따라서 다음 이동의 파이프 상태를 위의 3가지 조건에 따라 ..
BOJ 2156 · 포도주 시식 알고리즘 분류 : 다이나믹 프로그래밍 N개의 포도주 잔이 있을 때, 최대로 마실 수 있는 포도주의 양을 구해야 한다. DP를 이용하여 포도주 마시는 규칙에 따라 구현하면 된다. 포도주는 연속으로 3잔 이상 마실 수 없다. 즉, 연속하여 마실 수 있는 포도주는 최대 2잔이다.D[N] : N 번째 잔의 포도주를 마셨을 때, 최대로 마실 수 있는 포도주의 양 D[N]은 3가지 경우의 수로 나눌 수 있으며, 3가지 값 중 가장 큰 값이 D[N]이 된다.1. N 번째 잔을 마시지 않은 경우 : D[N-1]2. N 번째 잔이 연속 1잔째 마신 경우 : D[N-2] + P[N] (N-1 번째 잔은 마시지 않아야 한다.)3. N 번째 잔이 연속 2잔째 마신 경우 : D[N-3] + P[N-1] + P[N-1] (N-2..
BOJ 17135 · 캐슬 디펜스 알고리즘 분류 : 브루트 포스, 시뮬레이션 궁수를 성에 적절히 배치하여 적을 최대한 많이 죽이도록 구현하는 문제다. 가능한 궁수의 배치를 모두 만들고, 각 배치에서 적을 얼마나 쏴 죽일 수 있는지 카운트하면 된다. N*M 사이즈의 맵에서 궁수는 N+1번째 줄에 3명이 배치된다.궁수가 서로 겹치지 않도록, 3중 for문 또는 재귀를 통해 각각 배치한다. 조합 방식으로 구현하면 된다.그리고 배치한 위치의 인덱스를 별도로 저장한다. 아래의 코드에서는 archer 배열에 Y좌표(열 인덱스)가 저장되어 있다.각 배치에서 궁수로부터 적이 얼마나 떨어져 있는지 계산하고, 각 적을 죽여야 한다. 1. 궁수의 위치를 (N, K)라고 하고, 적의 위치를 (i, j)라고 하자. 단, (0≤i<N, 0≤j<M) 이다.2. 궁..
BOJ 9465 · 스티커 알고리즘 분류 : 다이나믹 프로그래밍 스티커를 떼어내어 얻을 수 있는 최대 점수를 DP를 이용하여 구해야 한다. D[N][M] : N번째 열에서 스티커를 M했을 때, 2xN 개의 스티커에서 얻을 수 있는 최대 점수M = 0 (위쪽 스티커를 뜯음), M = 1 (아래쪽 스티커를 뜯음), M = 2 (둘 다 뜯지 않음)D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = 0D[N][0] : N번째 열에서 위쪽 스티커를 뜯어서 얻은 최대 점수D[N][1] : N번째 열에서 아래쪽 스티커를 뜯어서 얻은 최대 점수D[N][2] : N번째 열에서 둘 다 뜯지 않고 얻은 최대 점수 C++ 소스코드 #include #include using namespace std; int n, d[1..
BOJ 2193 · 이친수 알고리즘 분류 : 다이나믹 프로그래밍 N자리 이친수를 DP를 통해 만들어야 한다. D[N] : N자리 이친수의 개수D[1] = 1, D[2] = 1D[N] = 0으로 끝나는 N-1자리 이친수 + 01로 끝나는 N-2자리 이친수 C++ 소스코드 #include int n; long long int d[91]; void solve() { d[1] = d[2] = 1; for (int i=3; i