링크 : https://www.acmicpc.net/problem/1149
여유있을 때, 어려운 문제 풀어보도록 하자.
연속되게 색깔이 칠해져서는 안된다. 이번 문제는 RGB 총 3가지의 경우가 있으므로 int ans = min(c1, min(c2,c3))
이런 식으로 진행해야 할 것 같다. 어떻게 해야 하는지 생각해보자.
N이 1000개 이므로 오류가 나면 long long 까지 고려해야겠다. 우선은 배열로 접근하자.
i번째 집을 확인(R로 칠했다고 가정)하기 위해서는 i-1번째 집의 색깔을 확인(G 또는 B)해야 한다. i-2번째 집은 i-1번째 집을 계산할 때 이미 계산되기 때문에 그 전까지는 고려하지 않아도 된다.
RGB를 선택했다는 것은 0, 1, 2로 표현하거나 arrR[i]를 0으로 바꿔줘야 할 것 같다. 아니면 바꾸면서 bool bR = true;
로 표현하여 if문을 구성할 때 if(bR) {G와 B만 고려함}
이런식으로 하는 것도 괜찮을 것 같다. 그럼 min을 못쓰겠구나.
#include<iostream>
#include<algorithm>
using namespace std;
int rgb[1001][3]{ 0, };
int cost[3]{ 0, };
int main() {
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> cost[0] >> cost[1] >> cost[2];
rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + cost[0];
rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + cost[1];
rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + cost[2];
}
cout << min(rgb[N][0], min(rgb[N][1], rgb[N][2]));
return 0;
}
오. 할말이 많다. 처음에 고려했을 때에는 if문을 사용해서 전에 무엇을 사용했는지 확인을 했었다. 예제 답은 나오는데 오답으로 뜨길래 #define ll long long int
를 선언하여 저번처럼 긴 정수로 인한 오답인 경우를 해결하려고 했는데 이 또한 오답이 떴다.
그래서 검색을 하고.. 보니 애초에 배열을 1001*3 배열
로 받아서 굳이 if문으로 전의 색을 확인하지 않고도 해결할 수 있었다.
rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + cost[0];
rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + cost[1];
rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + cost[2];
이렇게 rgb[i][0]
에는 현재 i
에 R이 들어간다고 가정한 후, 전 집 i-1
의 색깔 중에 가격이 적은 것을 선택하고 i에 들어가는 가격을 더해준 것이었다.
생각외로 dp문제는 이렇게 배열을 통해 해결한다.