1149번 RGB거리 BOJ 백준 C언어

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

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

출력

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

구현

이전값중 큰것 + 현재값을 해주면된다.
모든 동적 프로그래밍의 기본적인 개념이자 기초이다.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

int compare(int a, int b) {
    return (a >= b) ? b : a;
}

int main(void) {
    int num, i, min = 0;
    int arr[1000][3]; //입력받은 배열
    int temp[1000][3]; //DP할 배열
    scanf("%d", &num);

    for (i = 0; i < num; i++) {
        scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
    }
//DP 배열의 첫줄에는 입력받은거 그대로
    temp[0][0] = arr[0][0]; 
    temp[0][1] = arr[0][1];
    temp[0][2] = arr[0][2];

// i번째 DP배열의 a번은 i-1번째 DP배열 b,c번중 큰것과 현 배열 a번의 합  
    for (i = 1; i < num; i++) {
        temp[i][0] = compare(temp[i - 1][1], temp[i - 1][2]) + arr[i][0];
        temp[i][1] = compare(temp[i - 1][0], temp[i - 1][2]) + arr[i][1];
        temp[i][2] = compare(temp[i - 1][0], temp[i - 1][1]) + arr[i][2];
    }
// 셋 중 가장 작은 것 출력
    min = compare(temp[num - 1][0], temp[num - 1][1]);
    if (min < temp[num - 1][2]) printf("%d", min);
    else printf("%d", temp[num - 1][2]);
}