[BaekJoon] 1149번 : RGB 거리

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• DP를 이용하여 풀 수 있는 문제로 규칙을 잘 생각하면 됩니다.
• 2차원 배열을 만들고 행은 집의 수를 가리키고, 열은 3가지의 색상 크기로 선언합니다.
• i행 j열은 j색상을 칠한다고 가정했을 때, i 번째 집까지 집을 칠하는 최대 비용을 계산합니다.
• 첫 번째 행에서는 이전에 색을 칠한 집이 없기 때문에 자신의 색상을 칠하는 값으로 초기화합니다.
• 두 번째 행부터는 이전 행과 겹치지 않는 열 중에서 최대값을 설정하면 됩니다.
• ex) 2행 1열에서는 1행 2열과 1행 3열 둘 중 최대값에 2행 1열에 빨간집을 칠하는 값을 더하면 됩니다.

#include<iostream>
using namespace std;


int main(){
    int num;
    cin>>num;
    
    int arr[1005][3];
    for(int i=0;i<num;i++){
        for(int j=0;j<3;j++){
            cin>>arr[i][j];
        }
    }
    
    int sum[1005][3];
    sum[0][0] = arr[0][0];
    sum[0][1] = arr[0][1];
    sum[0][2] = arr[0][2];
    
    for(int i = 1;i<num;i++){
        sum[i][0] = min(sum[i-1][1], sum[i-1][2])+arr[i][0];
        sum[i][1] = min(sum[i-1][0], sum[i-1][2])+arr[i][1];
        sum[i][2] = min(sum[i-1][0], sum[i-1][1])+arr[i][2];
    }
    
    cout<<min(sum[num-1][0], min(sum[num-1][1], sum[num-1][2]));
}

• 추가로 궁금한점이나 수정할 부분 있으면 댓글로 남겨주세요.