본문 바로가기
Algorithm/백준

[백준 BOJ] 1149번 RGB 거리(자바/DP)

by 코딩로그 2022. 10. 17.

접근 방법

1. 조건에 따라 모든 집은 이웃의 색과 달라야 합니다.

 

2. 모든 칠해지는 경우의 수를 찾기

- 현재 빨간색으로 칠할 때 이전 집은 초록이거나 파랑이어야 합니다.

- 현재 파란색으로 칠하는 경우 이전 집은 빨간색이거나 초록이어야 합니다.

- 현재 초록색으로 칠하는 경우 이전 집은 빨간색이거나 파란색이어야 합니다.

 

따라서, 현재 색을 칠하기 위해서는 그 전 색깔 중에서 최소를 선택하면 됩니다. 현재 빨간 색을 칠하는 경우 이전 집은 초록이거나 파랑이어야하며 초록과 파랑 중 최소 비용을 선택하면 됩니다.

 

 

주의할 점

1. 처음으로 생각한 아이디어는 매번 최소 비용을 선택하는 방법입니다. 하지만, 이런 경우 이전 집까지의 최소 비용이 현재의 최소 비용을 보장하지는 않습니다. 따라서, 모든 칠해지는 경우의 수를 찾아 비용을 고려해야 합니다.

 

 

public class Main_1149 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine());
		
		int col = 3;
		int[][] maps = new int[N][col];
		
		for (int i = 0; i < maps.length; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < col; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][] dp = new int[N][col];
		dp[0][0] = maps[0][0]; dp[0][1] = maps[0][1]; dp[0][2] = maps[0][2];
		
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < col; j++) {
				if(j == 0) {//빨강->초록,파랑 가능
					dp[i][j] = Math.min(dp[i-1][j+1], dp[i-1][j+2]) + maps[i][j];
				}else if(j == 1) {//초록->빨강, 파랑 가능
					dp[i][j] = Math.min(dp[i-1][0], dp[i-1][2]) + maps[i][j];
				}else {//파랑->초록, 빨강 가능
					dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1]) + maps[i][j];
				}
			}
		}
		
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < col; i++) {
			result = Math.min(result, dp[N-1][i]);
		}
		
		System.out.println(result);
	}
}