[Silver I] RGB거리 - 1149 (DP)

[Silver I] RGB거리 - 1149

문제 링크

성능 요약

메모리: 30616 KB, 시간: 76 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

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보다 작거나 같은 자연수이다.

출력

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

풀이방법

붙어있는 집들끼리 색깔이 달라야 하므로 두 번째 집부터 탐색을 시작하여 바로 이전에 있는 집과 다른 색을 칠한 합 중 최솟값을 반복적으로 저장해주면 dp 알고리즘으로 인해 마지막집의 인덱스에 모든 집을 칠하는 비용의 최솟값이 저장된다.

마지막 집의 각 색깔마다 저장된 비용 중 가장 최솟값을 출력하면 해결.

-java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] dp = new int[n][3];
		for(int i = 0; i < n; i++) {
			String[] split = br.readLine().split(" ");
			for(int j = 0; j < 3; j++) {
				dp[i][j] = Integer.parseInt(split[j]);
			}
		}
		
		for(int i = 1; i < n; i++) {
			for(int j = 0; j < 3; j++) {
				if (j == 0) dp[i][j] = Math.min(dp[i][j] + dp[i-1][j+1], dp[i][j] + dp[i-1][j+2]);
				else if (j == 1) dp[i][j] = Math.min(dp[i][j] + dp[i-1][j-1], dp[i][j] + dp[i-1][j+1]);
				else if (j == 2) dp[i][j] = Math.min(dp[i][j] + dp[i-1][j-1], dp[i][j] + dp[i-1][j-2]);
			}
		}
		int answer = 10000000;
		for(int i = 0; i < 3; i++) {
			answer = Math.min(answer, dp[n-1][i]);
		}
		System.out.println(answer);
	}
}

-python

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))
for i in range(1,n):
    for j in range(3):
        if j == 0:
            graph[i][j] = min(graph[i][j] + graph[i-1][j+1], graph[i][j] + graph[i-1][j+2])
        elif j == 1:
            graph[i][j] = min(graph[i][j] + graph[i-1][j+1], graph[i][j] + graph[i-1][j-1])
        elif j == 2:
            graph[i][j] = min(graph[i][j] + graph[i-1][j-1], graph[i][j] + graph[i-1][j-2])
print(min(graph[-1]))