728x90
https://www.acmicpc.net/problem/1149
문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
코드1 (오답)
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>
using namespace std;
int N;
int house[1001][4];
int cost[4];
long long minn = 9999999999999;
void rgb(int n, int next, int sum){
sum += house[n][next];
if(sum > minn){
return;
}
if(n == N-1){
if(minn > sum){
minn = sum;
}
return;
}
if(next == 0){
rgb(n+1, 1, sum);
rgb(n+1, 2, sum);
}
else if(next == 1){
rgb(n+1, 0, sum);
rgb(n+1, 2, sum);
}
else if(next == 2){
rgb(n+1, 0, sum);
rgb(n+1, 1, sum);
}
}
int main() {
cin >> N;
for(int i=0; i<N; ++i){
for(int j=0; j<3; ++j){
cin >> house[i][j];
}
}
rgb(0, 0, 0);
rgb(0, 1, 0);
rgb(0, 2, 0);
cout << minn;
return 0;
}
처음에 동적 계획법을 무시하고 이렇게 짜봤다. 하지만 당연히 시간초과....
몇번을 더 생각한 후 결국 힌트를 봐버렸다...
코드2 (정답)
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>
using namespace std;
int N;
int house[1001][4];
int cost[4];
int main() {
cin >> N;
for(int i=1; i<=N; ++i){
for(int j=0; j<3; ++j){
cin >> cost[j];
}
house[i][0] = min(house[i-1][1], house[i-1][2]) + cost[0];
house[i][1] = min(house[i-1][0], house[i-1][2]) + cost[1];
house[i][2] = min(house[i-1][1], house[i-1][0]) + cost[2];
}
cout << min(house[N][0], min(house[N][1], house[N][2]));
return 0;
}
dp의 핵심은 문제를 쪼개는 것이다.
먼저 윗줄에서의 최소값에다가 자신의 값을 더하고 또 아래로 내려가서 이 동작을 반복하고 하다보면
최소값을 구할 수 있을 것이다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[1463] 1로 만들기 (0) | 2023.04.13 |
---|---|
[1932] 정수 삼각형 (0) | 2023.04.13 |
[1904] 01타일 (0) | 2023.04.01 |
[9184] 신나는 함수 실행 (0) | 2023.03.30 |
[11051] (C++) 이항 계수2 (0) | 2023.02.14 |