문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 디피로 접근할 수 있다.
  • 같은 색을 두번 연속 선택할 수 없으므로 각 지점에서 각 색깔을 선택했을 때의 최소값을 저장할 수 있어야 한다.
  • 이를 위한 어레이를 준비하고 전이 빨간색이었다면 현재 값의 초록색 값과 파란색의 값을 최신화시켜주도록 한다.

코드

#include <cstdio>
#include <vector>
using namespace std;
#define INF 1000001

int d[1003][3];
int rgb[1003][3];

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++)d[i][j] = INF;
    }
    for(int i = 0; i < n; i++) scanf("%d %d %d", &rgb[i][0], &rgb[i][1], &rgb[i][2]);
    d[0][0] = rgb[0][0], d[0][1] = rgb[0][1], d[0][2] = rgb[0][2];
    for(int i = 0; i < n; i++){
        if(d[i + 1][0] > d[i][1] + rgb[i+1][0]) d[i + 1][0] = d[i][1] + rgb[i+1][0];
        if(d[i + 1][0] > d[i][2] + rgb[i+1][0]) d[i + 1][0] = d[i][2] + rgb[i+1][0];
        if(d[i + 1][1] > d[i][0] + rgb[i+1][1]) d[i + 1][1] = d[i][0] + rgb[i+1][1];
        if(d[i + 1][1] > d[i][2] + rgb[i+1][1]) d[i + 1][1] = d[i][2] + rgb[i+1][1];
        if(d[i + 1][2] > d[i][0] + rgb[i+1][2]) d[i + 1][2] = d[i][0] + rgb[i+1][2];
        if(d[i + 1][2] > d[i][1] + rgb[i+1][2]) d[i + 1][2] = d[i][1] + rgb[i+1][2];
    }
    
    printf("%d", min(min(d[n][0], d[n][1]),d[n][2]));
}

느낀점

  • 코드를 더 읽기 쉽게 짤 수 있을 것 같은데 일단 한문제라도 더 풀어보고자 한다.