[BOJ/백준] 17404 RGB거리 2

● [문제번호 17404] RGB거리 2

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

17404번: RGB거리 2

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 1149 RGB거리 문제에서

1번 집과 N번 집의 색이 같지 않아야 한다는 조건이 추가되었다.

 

● 주의 할 것

: 1149 RGB거리 문제에서 좀 더 나아간 풀이일까 싶어서 고민했지만

구글링을 하니 조금 다르게 접근을 해야했다.

 

1149 RGB거리 에서 최소 비용을 구하는 방법을 동일하지만,

이번 문제에서는 출발점을 고려해야한다.

그래서 초기값부분에서 출발점만 정상적인 비용을 입력하고,

나머지 출발점은 매우 큰 값을 넣어,

누적된 최소비용이 모두 동일한 출발점으로 만드는 것이다.

색상은 3가지 이므로 이 과정을 3번 반복하면 된다.

 

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[index][color] : index집까지 index집을 color로 색칠하는 최소 비용

 

2. 점화식 찾기

→ 최소 비용을 구하는 방법은 동일

dp[home][0] = min(dp[home - 1][1], dp[home - 1][2]) + rgb[home][0];
dp[home][1] = min(dp[home - 1][0], dp[home - 1][2]) + rgb[home][1];
dp[home][2] = min(dp[home - 1][0], dp[home - 1][1]) + rgb[home][2];

 

3. 초기값 정하기

→ 출발점만 dp[index][color] = rgb[index][color]

 

 

● 참고 할 것

: 1149 RGB거리

https://pirateturtle.tistory.com/215

 

: 풀이과정 참고

https://tunafish78.tistory.com/91

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// rgb[index][color] : index집을 color로 색칠하는 비용
// dp[index][color] : index집까지 index집을 color로 색칠하는 최소 비용
// sol : 가장 큰 수로 두기 위해 1000*1000+1
int rgb[1001][3];
int dp[1001][3];
int N, sol = 1000 * 1000 + 1;

void program()
{
    // 각 출발색으로 반복
    for(int color = 0; color < 3; color++)
    {
        // 초기값
        for(int start = 0; start < 3; start++)
            if(start == color)
                dp[1][start] = rgb[1][start];
            else
                dp[1][start] = 1000 * 1000 + 1;
        
        // 점화식
        for(int home = 2; home <= N; home++)
        {
            dp[home][0] = min(dp[home - 1][1], dp[home - 1][2]) + rgb[home][0];
            dp[home][1] = min(dp[home - 1][0], dp[home - 1][2]) + rgb[home][1];
            dp[home][2] = min(dp[home - 1][0], dp[home - 1][1]) + rgb[home][2];
        }
        
        // 출발색이 아닌 경우에서 최소 비용 저장
        for(int end = 0; end < 3; end++)
            if(color != end)
                sol = min(sol, dp[N][end]);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 비용 입력
    for(int home = 1; home <= N; home++)
        for(int color = 0; color < 3; color++)
            cin >> rgb[home][color];
    
    program();
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [402 - 다이나믹 프로그래밍 1 (도전)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1309	동물원	https://pirateturtle.tistory.com/255
2	2225	합분해	https://pirateturtle.tistory.com/256
3	17404	RGB거리 2	https://pirateturtle.tistory.com/257