백준(BOJ) 동적프로그래밍 RGB거리 (1149) - Silver 1

https://www.acmicpc.net/problem/1149

1149번: RGB거리

문제

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보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

이 문제를 6개월 전부터 도전했었다.. 그 때 모두 실패해서 멘붕이었는데 이제는 DP와 함께 1트만에 성공했다.

일단 문제를 읽자마자 아 경우의 수를 계산하는 문제이라고 생각을 했다. 내가 경우의 수를 계산하는 문제는 접할 때는 

1. 그래프로 탐색이 가능한가?

-> 그래프순회(백트랙킹)

2. 그래프 탐색이 불가능

-> 그리디 또는 DP

6개월전에는 이 문제를 보고 상태공간 트리를 이용한 백트랙킹 기법으로 풀면 쉽게 풀릴것이라 생각했었다. 그래서 로직을 백트랙킹으로 겨우겨우 작성했지만 보기좋게 시간초과에 빠졌다. N값이 1000정도로 상당히 높은경우 백트랙킹을 사용하면 시간초과를 피할 수 없다는걸 그 때는 잘 몰랐던것 같다. 그래서 이번에는 다이나믹 프로그래밍 방법으로 접근했고 문제는 정말 쉽게 해결되었다. 

문제 해결

문제 해결 방식은 이전에 풀었던 삼성 기출 퇴사 문제와 비슷하게 해결했다.

2023.09.04 - [알고리즘/동적계획법(DP)] - 백준(BOJ) 동적프로그래밍(삼성 SW 역량 테스트 기출) 퇴사 (14501) - Silver 3

백준(BOJ) 동적프로그래밍(삼성 SW 역량 테스트 기출) 퇴사 (14501) - Silver 3

퇴사 문제는 DP테이블을 갱신하면서 최댓값을 찾는문제라면 이 문제는 DP테이블을 갱신하면서 최솟값을 찾는 문제이다. 

여기서 퇴사 문제와 마찬가지로 앞에서부터 계산하는 순방향방식으로 생각을하면 문제를 어떻게 풀지 막막하지만. 뒤에서부터 해결하는 워킹 백워드 방식의 생각으로 접근하면 아주아주 쉽게 해결이 가능하다. 일단 내가 세운 식은 다음과 같다.

문제에서 주어진 아래의 3개 조건을 만족하면서 각각의 RGB값을 갱신하는 방법이다.

식을 풀이하자면

- 현재 N에 있는 r값은 나보다 먼저 칠해진(N+1) 집 중에서 자기를 제외한 최솟값 + 자신의 값

- 현재 N에 있는 g값은 나보다 먼저 칠해진(N+1) 집 중에서 자기를 제외한 최솟값 + 자신의 값

- 현재 N에 있는 b값은 나보다 먼저 칠해진(N+1) 집 중에서 자기를 제외한 최솟값 + 자신의 값

위와 같이 테이블을 갱신하면 최종적으로 RGB 각각의 최솟값이 저장되어 있고 그 값 중 최솟값을 반환하면 해결가능 하다.

1. 먼저 테이블 갱신을 위해 나보다 먼저 칠해진 값들은 미리 처리해 준다.

dp[N-1] = rgb[N-1];

2. 반복문을 돌면서 위의 식을 이용하여 테이블 갱신

for(ll i=N-2; i>=0; i--){
        dp[i].r = min(dp[i+1].g, dp[i+1].b) + rgb[i].r;
        dp[i].g = min(dp[i+1].r, dp[i+1].b) + rgb[i].g;
        dp[i].b = min(dp[i+1].r, dp[i+1].g) + rgb[i].b;
    }

ex) 예제처럼 아래와 같은 input이 들어온다면

3
26 40 83
49 60 57
13 89 99

- 먼저 가장 마지막에 있는 색칠 비용을 dp 테이블에 갱신하면 다음과 같다.

- 다음 테이블을 갱신을 하면 다음과 같다 

 

dp_r(n) = min (g(n+1) , b(n+1) + r(n)

가장 먼저 칠한 g의 비용은 89, b의 비용은 99이다 따라서 r의 최솟값은 139이된다. 이와 같은 방식으로

b의 값은 13의 비용이드는 r과 89의 비용이 드는 g중에 r을 선택하고 자신을 칠한 70의 값이 갱신이 된다.

최종적으로 모든 테이블이 갱신이 되면 그 값 중에 가장 최솟값이 정답이 된다.

 

3. 최종값 중 최솟값 반환

ll min_value(){
    ll answer = INF ;
    if(dp[0].r < answer)
        answer = dp[0].r;
    if(dp[0].g < answer)
        answer = dp[0].g;
    if(dp[0].b < answer)
        answer = dp[0].b;
    return answer;
}

위의 방식으로 해결하면 시간초과를 피해 해결 할 수 있다. dp + 워킹백워드 무적인가...

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 1001
#define INF 2147483647

using namespace std;

typedef long long ll;;
typedef struct RGB{
    ll r;
    ll g;
    ll b;
}RGB;
vector<RGB>dp(SIZE);
ll min_value(){
    ll answer = INF ;
    if(dp[0].r < answer)
        answer = dp[0].r;
    if(dp[0].g < answer)
        answer = dp[0].g;
    if(dp[0].b < answer)
        answer = dp[0].b;
    return answer;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    ll N = 0;
    cin >> N ;
    vector<RGB>rgb(N);
    

    for(ll i=0;i <N; i++)
        cin >> rgb[i].r >> rgb[i].g >> rgb[i].b;

    dp[N-1] = rgb[N-1];
    
    for(ll i=N-2; i>=0; i--){
        dp[i].r = min(dp[i+1].g, dp[i+1].b) + rgb[i].r;
        dp[i].g = min(dp[i+1].r, dp[i+1].b) + rgb[i].g;
        dp[i].b = min(dp[i+1].r, dp[i+1].g) + rgb[i].b;
    }
    cout << min_value() << "\n";
    return 0;
}