출처 : https://www.acmicpc.net/problem/1149
RGB거리 성공 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (언어별 추가 시간 없음) | 128 MB | 19743 | 8531 | 6414 | 47.311% |
문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
예제 입력
3 26 40 83 49 60 57 13 89 99
예제 출력
96
힌트
>> 문제 풀이
dfs 를 이용하여 구현하였다.
하지만 매 단계 깊이가 진행할수록 2개의 자식 노드를 가지기 때문에, 백트래킹을 이용해야한다.
그대로 진행할 경우 21000번 만큼을 수행해야 한다다.
지금까지 거쳐온 노드들의 합을 저장하는 배열 mini_val 을 선언한다.
mini_val[level][i] 는 level 높이까지 지나오면서 level 높이의 색이 i를 가진 가장 최소의 값이다.
만약 이 값보다 작거나 같은 값을 가지고 있으면 , 이 노드부터는 동일한 경로를 지나기 때문에 굳이 dfs를 수행할 필요가 없다.
원리는 간단한데 세세한 구현에서 조금 막혀서 시간이 소비되었다.
여담 : 아직은 dfs와 dp 의 정확한 구분을 잘 못하겠다. ... 뭘 보고 dp 라고 느껴야 하는것인가??
>> 다른풀이
굳이 dfs를 쓸 필요 없이 각 높이별로 (bfs ) 같은 느낌으로 다음 단계의 누적 합을 갱신해준다.
이를 반복해서 수행하면 O(높이) 만큼의 시간 복잡도가 소요된다.
d[i][0] = Min(d[i-1][1], d[i-1][2]) + a[i][0];
d[i][1] = Min(d[i-1][0], d[i-1][2]) + a[i][1];
d[i][2] = Min(d[i-1][0], d[i-1][1]) + a[i][2];
위의 점화식을 지속적으로 갱신하는 것이다.
>> 소스
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> #define MAX 987654321 using namespace std; #pragma warning(disable: 4996) int N; int color_val[1000][3]; int mini_val[1000][3]; int mini = MAX; void dfs(int level, int nowNum, int sum) { // 합이 최소값보다 크면 종료 if (sum > mini) return; // 끝에 도달하면 종료 if ( level == N ) { if (sum < mini) mini = sum; return; } for (int i = 0; i < 3; i++) { // 색이 같으면 그냥 넘겨 if (i == nowNum) continue; // 방문한 곳의 값이 더 작거나 같으면 종료 if ( (mini_val[level][i] <= sum + color_val[level][i] ) ) continue; else mini_val[level][i] = sum + color_val[level][i]; // 다음 단계 dfs(level+1, i, mini_val[level][i]); } } int main() { // 숫자 입력 받기 cin >> N; for( int k = 0 ; k < N; k++){ for (int i = 0; i < 3; i++) { scanf( "%d" , &color_val[k][i]); mini_val[k][i] = MAX; } } for (int i = 0; i < 3; i++) { mini_val[0][i] = color_val[0][i]; } for (int i = 0; i < 3; i++) { dfs( 1 , i , color_val[0][i]); } cout << mini; return 0; } | cs |