[백준] 17404번: RGB거리2 Java

 

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

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

 

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

17404번: RGB거리 2

접근

원형 구조로 서로 이웃하는 집과 다른 색을 칠해야합니다.

선형의 경우에는 바로 이전 집과 다른 색을 칠하는 방법으로 최소값을 구할 수 있지만.

원형의 경우에는 마지막과 처음의 집 색을 고려해야 합니다.

 

처음 칠하는 집의 색을 지정한 뒤, 다음 집을 이전 색과 다른 색으로 집을 칠하는 방법 중 최소 비용으로 칠하는 방법을 저장합니다. (선형과 같은 방법)

마지막 집까지 이 과정을 완료했다면, 마지막 집을 처음 색과 다른 색을 칠한 경우 중 가장 비용이 적은 경우를 선택합니다.

이 과정을 처음 집의 색을 바꿔 반복합니다.

구현

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

public class Main {
	//https://www.acmicpc.net/problem/17404
	static final int INF = 987654321;
	
	public static int solution(int n, int[][] rgbs) {
		//최대 비용으로 초기화
		int answer = INF;
		//비용을 저장할 dp, i번째 집을 r/g/b로 칠할 경우, 최소 비용을 저장
		int[][] dp = new int[n][3];
		
		//i : 처음 색을 지정
		for(int i=0;i<3;i++) {
			//처음 i번째 색을 선택하기 위해, i번째 색 이외 INF로 초기화
			for(int j=0;j<3;j++) {
				dp[0][j]=i==j?rgbs[0][i]:INF;
			}
			//집 탐색
			for(int j=1;j<n;j++) {
				//이전 집과 다른 색을 칠하는 경우 중 최소값을 저장
				for(int k=0;k<3;k++) {
					dp[j][k]=INF;
					for(int l=0;l<3;l++) {
						if(k==l) continue;
						dp[j][k]=Math.min(dp[j][k], dp[j-1][l]+rgbs[j][k]);
					}
				}
			}
			//처음과 마지막집의 색이 다르면 최소값을 answer로 가져오기
			for(int j=0;j<3;j++) {
				if(i==j) continue;
				answer=Math.min(answer, dp[n-1][j]);
			}
		}
		//출력
		return answer;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); //집의 개수
		StringTokenizer st;
		int[][] rgbs = new int[n][3]; //각 색을 칠하는 비용
		//비용 입력
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			rgbs[i][0]=Integer.parseInt(st.nextToken());
			rgbs[i][1]=Integer.parseInt(st.nextToken());
			rgbs[i][2]=Integer.parseInt(st.nextToken());
		}
		//최소 비용 출력
		System.out.println(solution(n, rgbs));
		
		br.close();
	}
}