[01149] RGB거리

[01149] RGB거리

문제

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 <iostream>

using namespace std;

/* 조건 */
#define MAXINPUT 1001

/* 변수 */
int N, cost[MAXINPUT][3];

/* 함수 */
// 두 수 중 최솟값을 return해주는 함수
int min(int a, int b) {
    return a<b?a:b;
}

int main() {
    /* 입력 */
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%d%d%d", &cost[i][0], &cost[i][1], &cost[i][2]);
    }

    /* 풀이 */
    // N = 2부터 N까지 앞서 구한 값들 중 현재 선택한 선택지를 제외한 최솟값과 더해줌
    for(int i = 2; i <= N; i++) { //N = 1은 앞의 집이 없으므로 2부터 시작
        cost[i][0] += min(cost[i-1][1], cost[i-1][2]);
        cost[i][1] += min(cost[i-1][0], cost[i-1][2]);
        cost[i][2] += min(cost[i-1][0], cost[i-1][1]);
    }

    /* 출력 */
    printf("%d\n", min(min(cost[N][0], cost[N][1]), cost[N][2]));
}

풀이과정

논리

이 문제는 앞의 결과가 뒤의 결과에 따라 바뀔 수 있다.

• (예시)

N	0	1	2
1	1	2	3
2	2	1	3
3	1	2	3
4	1	9	9

위의 경우 N = 3단계 까지 최솟값을 찾아냈어도 N = 4단계 에서 최솟값을 구해보면 위의 선택지를 모두 바꿔야 한다.

따라서 아래와 같이 각 단계마다 각 선택지에 대한 최솟값을 찾아 모든 경우를 고려하면서 진행하다보면 끝까지 최솟값을 찾을 수 있을 것이다.

N	0	1	2
1	a₁	b₁	c₁
2	a₂ + min(b₁, c₁)	b₂ + min(a₁, c₁)	c₂ + min(a₁, b₁)
3	a₃ + min(b₂, c₂)	b₃ + min(a₂, c₂)	c₃ + min(a₂, b₂)
4	a₂ + min(b₃, c₃)	b₂ + min(a₃, c₃)	c₂ + min(a₃, b₃)
...	...	...	...
n	aₙ + min(bₙ₋₁, cₙ₋₁)	bₙ + min(aₙ₋₁, cₙ₋₁)	cₙ + min(aₙ₋₁, bₙ₋₁)

위와 같이 N까지 진행해준 후 aₙ, bₙ, cₙ 중 최솟값이 답이 될 것이다.

함수

• int min(int a, int b)
  a와 b중 작은 값을 return하는 함수

출처

백준 01149번 RGB거리
https://www.acmicpc.net/problem/1149