Baekjoon1149: RGB거리

RGB거리

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

68150

33495

24925

48.906%

문제

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

출력

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

 

풀이

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

여기서 힌트를 발견할 수 있다. 동적 계획법이 익숙한 사람은 빠르게 풀 수 있지만 현재 학습 중인 내게 생각하기 매우 어려운 방식이었다. 문제는 며칠 전에 보고 다른 문제로 우선 넘어갔다 그 후 LIS, LCS 등의 문제들을 접하면서 DP에 조금 익숙해지고 난 뒤 풀게되었다.

1) dp[N]값이 기록되어있지 않을 때만 연산한다

→ 동적계획법 특히 Top → Bottom에서 기본적으로 조건문을 사용하는 듯 하다

2) 각각의 색(R,G,B)을 통해 현재항을 표현한다

→ 현재항에서 사용하는 색을 R이라고 하면, 이전항은 G 또는 B의 값을 가져야한다

→ 그 두 값 중에서 최소값을 채택한다. 여기서 사용하는 메소드가 Math의 min이다

→ dp[N][R]= Math.min( House(N-1, G), House(N-1, B) );

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	static Integer[][] dp;
	static int[][] cost;
	public static int House(int N, int color) {
	if(N==0) {
		return dp[0][color]; // N=0일 때는 dp배열의 값을 리턴
	}
	if(dp[N][color]==null) {
		switch(color) { //Math.min을 통해 재귀로 비교해 값을 가져온다
		case 0: dp[N][color]=Math.min(House(N-1,1)+cost[N][color], House(N-1,2)+cost[N][color]);break;
		case 1: dp[N][color]=Math.min(House(N-1,0)+cost[N][color], House(N-1,2)+cost[N][color]);break;
		case 2: dp[N][color]=Math.min(House(N-1,0)+cost[N][color], House(N-1,1)+cost[N][color]);break;
		}
	}
		return dp[N][color];
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int N = Integer.parseInt(br.readLine());
	cost = new int[N][3]; //0:R, 1:G, 2:B
	dp = new Integer[N][3];
	for(int i=0; i<N;i++) {
		st = new StringTokenizer(br.readLine()," ");
		for(int j=0; j<3; j++) {
			cost[i][j]=Integer.parseInt(st.nextToken());
		}
	} //cost 배열 안에 입력값들 넣어주기
	
	dp[0][0]=cost[0][0];
	dp[0][1]=cost[0][1];
	dp[0][2]=cost[0][2];
	//초기값 넣어주기

	System.out.print(Math.min(House(N-1,0), Math.min(House(N-1,1), House(N-1,2))));
	}
 
}