[백준BOJ] 17404번 RGB거리2.java

 

백준 저지에서 RGB거리2를 자바를 통해 풀어 보았다. 

 

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

17404번: RGB거리 2

 

17404번 RGB거리2.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

17404번 RGB거리 2 

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

설명

dp를 통해서 풀 수 있다.

 

대부분의 조건은 RGB거리와 똑같다. 다른 점은 1과 N의 집이 달라야 하는 것이다. 

 

RGB거리 문제에서는 i의 색을 정하기 위해서 i-1의 색만 알면 되었다. RGB거리2에서는 N의 색을 정하기 위해서 1번 집의 색도 알고 있어야 한다. 따라서 1번 집의 색을 고정시킨다.

 

1번 집의 색을 고정시키기 위해서는 다른 색을 절대 선택되지 않도록 하면 된다. 예를 들어 1번 집의 색을 R로 정해놓는 다면 G와 B는 절대 선택되지 못하도록 1번 집의 G와 B의 비용을 최댓값으로 초기화시킨다. 

 

즉 1번 집이 각각 R,G,B로 선택되었을 때를 따로 구한다. 따라서 반복문을 3번 돌려야한다.

코드

//17404번 RGB거리2.java
package boj20211216;

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

public class RGB거리2_17404 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static final int MAX=1000*1000+1;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[][] RGB = new int[N+1][3];
		int[][] dp = new int[N+1][3];
		
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j=0;j<3;j++)RGB[i][j]=Integer.parseInt(st.nextToken());
		}
		
		
		int min = MAX;
		
		for(int start=0;start<3;start++) {
			for(int i=0;i<3;i++) {
				//시작하는 집을 start로 고정
				if(start==i)dp[1][i]=RGB[1][i];
				else dp[1][i]=MAX;
			}
			//중간 과정
			for(int i=2;i<=N;i++) {
				dp[i][0] = RGB[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
				dp[i][1] = RGB[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
				dp[i][2] = RGB[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
			}
			//start를 제외한 수 중 가장 작은 수 선택
			for(int i=0;i<3;i++) {
				if(i!=start && min>dp[N][i]) {
					min = dp[N][i];
				}
			}
		}
		System.out.println(min);
		
	}
    
    
}