[BOJ] #1149 RGB 거리

시간 제한	메모리 제한	정답 비율
0.5 초	128 MB	46.756%

 

1149번: RGB거리

문제

N개의 행에 대하여 해당 행(집)을 빨간색, 초록색, 파란색으로 칠할 때 드는 비용이 각각 주어진다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

모든 집을 칠하는 비용의 최솟값을 구해야 한다.

N은 최대 1000 이다.

 

방법

오랜만에 dp를 푸려니 머리가 안돌아가서 2년 전에 풀었던 내 코드를 봤다... (포스팅은 이게 나중이지만 1010 다리놓기 보다 이전에 품..)

dp는 통찰력이다!!
i 번째에서 r을 선택할 때는 i-1번째에서 g또는 b를 선택해야 하니까 i-1 번째까지의 g또는 b 중 값이 작은 것을 선택해야한다.

 

메모리	시간
1988 KB	0 ms

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, r, g, b, x, y, z, ans;
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &r, &g, &b);
        r = min(y, z) + r;
        g = min(x, z) + g;
        b = min(x, y) + b;
        x = r, y = g, z = b;
    }
    ans = min(x, min(y, z));
    printf("%d", ans);
    return 0;
}

 

이 코드를 보고 dp 1차원 배열을 이용해서 풀어볼까 했는데, dp[r], dp[g], dp[b] 를 각각 비교해야하는데 이미 갱신된 값으로 비교하게 되어 변수를 더 써야하는 상황이고 그러려면 2차원 배열로 하는게 더 직관적이라고 생각이 들어 변수 3개만 사용할 수 있는 위의 방법이 베스트인것 같다.

1차원 배열로 풀어볼까 했던 코드가 궁금하다면 여기로