[백준/C++] 1149번 : RGB 거리 풀이

문제 1149 : RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

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

 

 

위 문제는 프로그래머스 땅따먹기(https://programmers.co.kr/learn/courses/30/lessons/12913) 와 비슷한 문제다.

전형적인 DP 문제 ‼️

 

열이 3개로 고정이므로 (R,G,B)

 

1. R을 선택했을 경우(열 0을 선택했을 경우) 이 전의 G,B 칸 중(열 1,2) 최소를 선택해 저장한다.
2. G을 선택했을 경우(열 1을 선택했을 경우) 이 전의 R,B 칸 중(열 0,2) 최소를 선택해 저장한다.
3. B을 선택했을 경우(열 2을 선택했을 경우) 이 전의 R,G 칸 중(열 0,1) 최소를 선택해 저장한다.

 

 

문제 풀이

#include <iostream>

using namespace std;

int map[1001][1001];

int min(int a, int b){
    return a < b ? a : b;
}

int main(void){
    
    int n;
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++){
            cin >> map[i][j];
        }
    }
    
    for(int i=1; i<n; i++){
        map[i][0] += min(map[i-1][1], map[i-1][2]);
        map[i][1] += min(map[i-1][0], map[i-1][2]);
        map[i][2] += min(map[i-1][0], map[i-1][1]);
        
    }
    
    cout << min(min(map[n-1][0], map[n-1][1]), map[n-1][2]) << endl;
    
    return 0;
}

 

 

풀이 인증