[백준/JAVA] 17404번: RGB거리 2

📖 문제

17404번: RGB거리 2

 

 

 

 

💡  풀이 방식

• DP

dp[ i ][ j ] = k
⇒ 1~i번째 집까지 칠하고 i번째 집은 j색으로 칠했을 때의 최소 비용은 k

 

 

1. 첫 집에 칠할 색 k를 정한다. 그러고 나면 나머지 색으로는 첫 집을 칠할 수 없으므로 나머지 칸들은 최댓값으로 설정한다. (0: 빨강 / 1: 초록 / 2: 파랑)

→ dp[1][0] : 첫 집을 빨간색으로 칠함. 나머지 dp[1][1] = dp[1][2] = INF

→ dp[1][1] : 첫 집을 초록색으로 칠함. 나머지 dp[1][0] = dp[1][2] = INF

→ dp[1][2] : 첫 집을 파랑색으로 칠함. 나머지 dp[1][0] = dp[1][1] = INF

for(int i = 0 ; i < 3 ; i++) {
    dp[1][i] = (i == k) ? rgb[1][i] : INF;	// k: 첫 집에 칠하기로 정한 색상
}

 

 

2. 두 번째 집부터 색칠한다.

for(int i = 2 ; i <= N ; i++) {
    dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
    dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + rgb[i][1];
    dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
}

 

 

3. 마지막 집은 첫 집과 같은 색을 칠할 수 없으므로 첫 집의 색에 따라 마지막 집의 남은 두 색깔 중 더 작은 값을 구한다.

- 첫 집이 빨강색이면, 마지막 집은 초록/파랑으로 칠한 dp 값 중 최솟값 구함

- 첫 집이 초록색이면, 마지막 집은 빨강/파랑으로 칠한 dp 값 중 최솟값 구함

- 첫 집이 파랑색이면, 마지막 집은 빨강/초록으로 칠한 dp 값 중 최솟값 구함

for(int i = 0 ; i < 3 ; i++) {
    if(k != i)  // 첫 집 색 != 마지막 집 색
        answer = Math.min(answer, dp[N][i]);
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int INF = 1000*1000 +1;
    
    static int N;
    static int[][] rgb, dp;
    static int answer = INF;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        rgb = 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());
            }
        }
        
        dp = new int[N+1][3];
        for(int k = 0 ; k < 3 ; k++) {  // 0: RED / 1: GREEN / 2: BLUE
            // 초기화: 첫 번째 줄의 i번째 집에는 i색을 칠함
            for(int i = 0 ; i < 3 ; i++) {
                dp[1][i] = (i == k) ? rgb[1][i] : INF;
            }
            
            for(int i = 2 ; i <= N ; i++) { // 2번째 집부터 색칠
                dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + rgb[i][1];
                dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
            }
            
            // 정답 최솟값 구하기
            for(int i = 0 ; i < 3 ; i++) {
                if(i != k)  // 첫 집 색 != 마지막 집 색
                    answer = Math.min(answer, dp[N][i]);
            }
        }
        
        System.out.println(answer);
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

엇 내가 풀려고 생각했던 방식과 비슷하심

백준 17404번 RGB거리 2 [JAVA]

---

💦 어려웠던 점

- DP인 건 캐치했고, 심지어 점화식도 제대로 세웠는데 초기값을 어떻게 설정하지?의 문제..

- 처음 / 중간/ 끝으로 나눠 색깔이 어떻게 겹치지 않게 해야할지 고민되었다...

 

 

🧐 새로 알게 된 내용

- 첫 번째 집에는 그냥 i색을 칠하자...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔

[백준 17404: JAVA] RGB거리 2 / 동적 프로그래밍

 

백준 17404번 RGB거리 2 [JAVA]