백준, BOJ, 17404번, RGB거리 2 C++ [CPP] ★★★

전형적인 DP 문제다.

다만 조건을 곁들인?

DP인 것을 쉽게 파악하였으나 조건을 만족시키려면 어떻게 해야하는가를 좀 많이 고민했다.

 

결국 하나씩 3개 돌리는 것이 답이었다.

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

 

---

 

#맞는 풀이

#include <bits/stdc++.h>


#define R 0
#define G 1
#define B 2

using namespace std;

const int MAX = 1002;

int cost[MAX][3];
int house[MAX][3];



int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int num;
    cin >> num;
    for(int i = 1; i<=num; i++){
        for(int j = 0; j<3; j++)
        cin >> cost[i][j];
        
    }
    
    int ans = 123456789;// 충분히 큰 값
    
    
    //첫번째 집 색
    for(int k = 0; k<3; k++){
        //색
        for(int j = 0; j<3; j++){
            //초기값 설정
            if(j == k){
                house[1][j] = cost[1][j];
            }else{
                //집 색깔이 다른 집들은 계산에 포함 안 되게 큰 값
                house[1][j] = 123456789;
            }
        }
        
        //모든 색에 대해서 조사
        for(int i = 2; i<=num; i++){
            house[i][R] = min(house[i-1][G], house[i-1][B]) + cost[i][R];
            house[i][G] = min(house[i-1][R], house[i-1][B]) + cost[i][G];
            house[i][B] = min(house[i-1][R], house[i-1][G]) + cost[i][B];
        }
        
        //결과 중 어떤 집이 가장 최솟값인지 조사
        for(int j = 0; j<3; j++){
            if(j == k) continue;//첫번째 집과 색이 같으면 안 됨
            ans = min(ans, house[num][j]);
        }
    }
    
    
    cout << ans << '\n';
    
    return 0;
}

 

 

num에서는 마지막 집 색 모두에 대해 조사하지만

for 문에서 첫번째 집과 같은 색을 걸러낸다.