문제 풀이

[c++] 백준 17404 RGB거리 2

미분당한 적분상수 2023. 3. 23. 02:07

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

 

17404번: RGB거리 2

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

www.acmicpc.net

1149번 RGB거리(https://www.acmicpc.net/problem/1149)와 풀이는 같지만, 1번 집과  N번 집의 색이 다른 경우를 모두 해본다.

그 경우들은

빨강, 파랑

빨강, 초록

초록, 빨강

초록, 파랑

파랑, 빨강

파랑, 초록

와 같다.

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000*1000+1
int arr[1010][3];
int dp[1010][3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    int ans = MAX;
    for(int i=0; i<n; i++)
        for(int j=0; j<3; j++)
            cin>>arr[i][j];
    for(int k=0; k<3; k++){ // 1번 집의 색을 k로 고정
        for(int j=0; j<3; j++){ // dp배열 초기값
            if(k == j)
                dp[0][j] = arr[0][j];
            else
                dp[0][j] = MAX;
        }
        //dp 점화식 돌리기
        for(int i=1; i<n; i++){
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
        }
        for(int t=0; t<3; t++){ // N번 집 색 t로 정하기
            if(t == k) // 1번 집과 N번 집 색이 같으면 스킵
                continue;
            ans = min(ans, dp[n-1][t]);
        }
    }
    cout << ans;
    return 0;
}

'문제 풀이' 카테고리의 다른 글

[c++] 백준 2109 순회 강연  (0) 2023.04.14
[c++] 백준 2812 크게 만들기  (0) 2023.04.14
[c++] 백준 13398 연속합 2  (0) 2023.03.22
[c++] 백준 15988 1, 2, 3 더하기 3  (0) 2023.03.20
[c++] 백준 1309 동물원  (0) 2023.03.20