[ 백준 1149 - RGB 거리 ]

문제 분석

1. DP

시간 복잡도

구현

테이블 정의

D[i][1] == i번째까지 색칠을 마쳤고 i번째 집을 R로 색칠 했을 경우
D[i][2] == i번째까지 색칠을 마쳤고 i번째 집을 G로 색칠 했을 경우
D[i][3] == i번째까지 색칠을 마쳤고 i번째 집을 B로 색칠 했을 경우

점화식 정의

D[i][1] = min(D[i-1][2], D[i-1][3]) + score[i][1];
D[i][2] = min(D[i-1][1], D[i-1][3]) + score[i][2];
D[i][3] = min(D[i-1][1], D[i-1][2]) + score[i][3];

• score[i][RGB_cost] = i번째 집을 칠할 때의 비용 ( 문제의 입력 값 )

초기값의 정의

D[1][1] = score[1][1]
D[1][2] = score[1][2]
D[1][3] = score[1][3]

헤맸던 부분

헤맸던 곳은 딱히 없다.

얻은 것

DP 유형 학습

전체 코드 [ 내 코드 ]

#include <iostream>
using namespace std;

int board[1002][5]; // 1-indexed
int score[1002][5]; // 1-indexed

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int N;

void get_input(){
    cin >> N;
    for(int i = 1 ; i <= N; i++)   {
        cin >> board[i][1];
        cin >> board[i][2];
        cin >> board[i][3];
    }
}


int main(void){
    init();
    get_input();


    score[1][1] = board[1][1];
    score[1][2] = board[1][2];
    score[1][3] = board[1][3];

    for(int i = 2 ; i <= N; i++){
        score[i][1] = min(score[i-1][2], score[i-1][3]) + board[i][1];
        // R
        score[i][2] = min(score[i-1][1], score[i-1][3]) + board[i][2];
        // G
        score[i][3] = min(score[i-1][1], score[i-1][2]) + board[i][3];
        // B
    }

    int ans = score[N][1];
    for(int i = 2; i <= 3; i++){
        ans = min(ans,  score[N][i]);
    }

    cout << ans << "\n";

    return 0;
}

느낀점

DP는 유형 양치기...?

참조

바킹독님의 유튜브 강의

유튜브 강의 영상
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.