💡 다이나믹 프로그래밍
Memory 2044KB Time 0ms Code Length 747B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
int N;
int map[1000][3]; // 집을 색칠하는데 드는 비용
int dp[1000][3];
int result = 1e9;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 3; j++) {
cin >> map[i][j];
}
}
}
void solved() {
for (int i = 0; i < 3; i++) {
dp[0][i] = map[0][i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < 3; j++) {
int minV = 1e9;
for (int k = 0; k < 3; k++) {
if (k == j) continue;
int tmp = map[i][j] + dp[i - 1][k];
minV = minV > tmp ? tmp : minV;
}
dp[i][j] = minV; // 최솟값적용
}
}
for (int i = 0; i < 3; i++) {
result = result > dp[N - 1][i] ? dp[N - 1][i] : result;
}
}
int main() {
init();
solved();
cout << result;
}
이 코드는 N개의 집을 색칠하는데 드는 비용을 계산하는 프로그램이다. init 함수에서는 N과 각 집을 색칠하는데 드는 비용을 입력받고, solved 함수에서는 각 집을 색칠할 때 이전 집의 색과 겹치지 않도록 최소 비용을 계산한다. 이를 위해 dp 배열을 사용하여 이전 집까지의 최소 비용을 저장하고, 현재 집을 색칠할 때 최소 비용을 계산하여 dp 배열을 업데이트한다. 마지막으로 모든 집을 색칠한 후의 최소 비용을 result에 저장하고 출력한다.
