[Python/Java] 백준 1149번 - RGB거리

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

1149번: RGB거리

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍(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보다 작거나 같은 자연수이다.

출력

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

 

 

---

처음엔 단순히 반복문 돌면서 최솟값만 구해주면 되는 줄 알았다.

 

하지만 예를들어

 

1 100 200
1 201 101
202 102 1

이런 입력이 들어올 경우

1 + 101 + 102 = 204가 된다.

 

정답은 100 + 1 + 1 = 102가 되어야 한다.

 

그래서 처음부터 각각 집을 골랐을 모든 경우의 수를 생각하며 최솟값을 찾아야 한다.

---

Python

import sys
input = sys.stdin.readline
n = int(input())
house = [ [0] * 3 for _ in range(1001) ]

for i in range(1, n+1):
    r, g, b = map(int ,input().split())
    house[i][0] = min(house[i-1][1], house[i-1][2]) + r
    house[i][1] = min(house[i-1][0], house[i-1][2]) + g
    house[i][2] = min(house[i-1][0], house[i-1][1]) + b
    
print(min(house[n]))

N의 범위가 2 ~ 1000까지 이므로 1001로 선언하고 0번째 배열을 0으로 초기화한다.

 

그리고 경우의 수를 모두 구해준다.

 

1. 첫 번째 집을 고른 경우
   • i -1번째의 두 번째 집과 세 번째 집 중 최소값을 구해 첫번째 집의 비용을 더한다
2. 두번째 집을 고른 경우
   • i - 1번째의 첫번째 집과 세번째 집 중 최소값을 구해 두번째 집의 비용을 더한다.
3. 세번째 집을 고른 경우
   • i -1번째의 첫번째 집과 두번째 집 중 최소값을 구해 세번째 집의 비용을 더한다.

위를 코드로 구현한 것이

 

    house[i][0] = min(house[i-1][1], house[i-1][2]) + r
    house[i][1] = min(house[i-1][0], house[i-1][2]) + g
    house[i][2] = min(house[i-1][0], house[i-1][1]) + b

위와 같다.

 

---

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int [][] house = new int [1001][n];
		house[0][0] = 0;
		house[0][1] = 0;
		house[0][2] = 0;
		
		for(int i=1; i<n+1; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			house[i][0] = Min(house[i-1][1], house[i-1][2]) + r;
			house[i][1] = Min(house[i-1][0], house[i-1][2]) + g;
			house[i][2] = Min(house[i-1][0], house[i-1][1]) + b;
		}
		System.out.println(Min(Min(house[n][0], house[n][1]), house[n][2]));
	}
	static int Min(int a, int b) {
		if( a > b )
			return b;
		else
			return a;
	}
}