[백준(Baekjoon)][자바(java)] 1149 : RGB거리 / 동적 계획법 1

 

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

1149번: RGB거리

 

* 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

* 풀이 방법

▶  N개의 집이 있고, 색깔이 3가지이므로 N*3인 2차원 배열 생성

    ( 입력받은 배열에 그대로 해도 됨. 왜냐면 값이 따로 필요한 게 아니라 입력받은 값이 비용이고,

      비용의 합을 구하는 문제이기 때문 )

▶  n번째 집은 n-1번째 집과 색깔이 같을 수 없다는 조건을 이용하여,

     n번째 집의 색이 0(빨)일 때, N-1번째 집의 1(초) 또는 2(파) 중 비용이 적은 것을 더함

                                   1(초)                                          0(빨)          2(파)

                                   2(파)                                          0(빨)          1(초)

     마지막 번째에 오게 되면 비용들의 총 합이 만들어지는데, 그 3개 중 최솟값이 답이 됨

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;

		int n = Integer.parseInt( br.readLine() ), i, j;
		int dp[][] = new int[n][3];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ )
				dp[i][j] = Integer.parseInt( st.nextToken() );
		}
        br.close();

		for( i = 1; i < n; i++ ) {
			dp[i][0] += Math.min( dp[i-1][1], dp[i-1][2] );
			dp[i][1] += Math.min( dp[i-1][0], dp[i-1][2] );
			dp[i][2] += Math.min( dp[i-1][0], dp[i-1][1] );
		}
		
		System.out.println( Math.min( Math.min( dp[n-1][0], dp[n-1][1] ) , dp[n-1][2] ) );
	}

}