[BOJ/백준] 1149 RGB거리

● [문제번호 1149] RGB거리

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

1149번: RGB거리

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

dp[index][0] : RED를 칠한 index집까지 총 비용

dp[index][1] : GREEN를 칠한 index집까지 총 비용

dp[index][2] : BLUE를 칠한 index집까지 총 비용

 

2. 점화식 찾기

→ 해당 색상을 제외한 바로 전 집의 총 비용에 해당 색상 비용 추가

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

 

3. 초기값 정하기

→ 맨 처음 집은 입력된 RED, GREEN, BLUE 가격 그대로

dp[1][0] = rgb[1][0];
dp[1][1] = rgb[1][1];
dp[1][2] = rgb[1][2];

 

예제 입력1 구하는 방법

 

 

● 주의 할 것

: NULL

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// rgb : 각 집의 RED, GREEN, BLUE 색상 비용 저장
// dp : index집까지 RED, GREEN, BLUE 색상 칠하는 총 비용
int rgb[1001][3];
int dp[1001][3];
int N;

void color()
{
    // 초기값
    dp[1][0] = rgb[1][0];
    dp[1][1] = rgb[1][1];
    dp[1][2] = rgb[1][2];
    
    // 점화식
    for(int index = 2; index <= N; index++)
    {
        dp[index][0] = min(dp[index - 1][1], dp[index - 1][2]) + rgb[index][0];
        dp[index][1] = min(dp[index - 1][0], dp[index - 1][2]) + rgb[index][1];
        dp[index][2] = min(dp[index - 1][0], dp[index - 1][1]) + rgb[index][2];
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 색상 비용 입력
    for(int n = 1; n <= N; n++)
        cin >> rgb[n][0] >> rgb[n][1] >> rgb[n][2];
    
    color();
    
    // 마지막 집의 RED, GREEN, BLUE 중에 최솟값
    cout << min(dp[N][0], min(dp[N][1], dp[N][2]));
    
    return 0;
}

 

 

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

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225