[백준 1149]RGB거리 - 자바

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

1149번: RGB거리

 

1. 풀이

---

 

문제의 조건을 보면 i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다고 나와있습니다.

 

전형적인 DP문제이며, RGB 3가지 색으로 구별하였으므로 3가지 방향으로 나누어 접근하도록 합니다.

 

즉, 3가지 방향으로 접근하여 N번째 까지의 드는 비용들을 전부 메모이제이션하고, 마지막에 N번째의 최소 값을 구하면 됩니다.

 

	R	G	B
1번 집	26	40	83
2번 집	49	60	57
3번 집	13	89	99

위와 같은 입력 값을 아래와 같이 DP로 풀어줍니다. 

for(int i = 1; i <= n; i++){
	memo[i][0] = min(memo[i-1][1], memo[i-1][2]) + input[i][0]; // 0번째
	memo[i][1] = min(memo[i-1][0], memo[i-1][2]) + input[i][1]; // 1번째
	memo[i][2] = min(memo[i-1][0], memo[i-1][1]) + input[i][2]; // 2번째
}

 

즉, 아래와 같은 결과가 나온다.

	R	G	B
1번 집	26	40	83
2번 집	89	86	83
3번 집	96(정답)	172	105

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int min(int a, int b) {
		if(a > b)
			return b;
		else
			return a;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[][] nums = new int[num+1][3];
		int[][] memo = new int[num+1][3];
		
		
		for(int i = 1; i <= num; i++) {
			for(int j = 0; j < 3; j++) {
				nums[i][j] = sc.nextInt();
				memo[i][j] = nums[i][j];
			}
		}
		
		for(int i = 1; i <= num; i++) {
			memo[i][0] = min(memo[i-1][1], memo[i-1][2]) + nums[i][0];
			memo[i][1] = min(memo[i-1][0], memo[i-1][2]) + nums[i][1];
			memo[i][2] = min(memo[i-1][0], memo[i-1][1]) + nums[i][2];
		}	
		
		System.out.println(min(min(memo[num][0], memo[num][1]),memo[num][2]));
		
		sc.close();
		return;
	}
}