RGB거리 : 1149번 - JAVA

---

1. 문제 링크

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

1149번: RGB거리

 

---

2. 문제 설명

 

---

3. 문제 접근

문제의 조건 파악하는 것이 가장 중요하다고 생각한다.

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

(※이것이 문제의 핵심.)

 

1. 문제의 접근을 단계화해서 문제를 접근하는 것이 필요하다.

-변 길이와 겹치지 않도록 하는 경우면 3가지 경루로 나눌 수 있다.

(1) dp[i][1] → dp[i-1][2] 와 dp[i-1][3]의 최대값을 파악

(2) dp[i][2] → dp[i-1][1] 와 dp[i-1][3]의 최대값을 파악

(3) dp[i][3] → dp[i-1][1] 와 dp[i-1][2]의 최대값을 파악

 

2, 해당 문제 접근을 단계화한 작업의 점화식을 작성한다.

(1) dp[i][1] → Math.max(dp[i-1][2] + dp[i-1][3]);

(2) dp[i][2] → Math.max(dp[i-1][1] 와 dp[i-1][3]);

(3) dp[i][3] → Math.max(dp[i-1][1] 와 dp[i-1][2]);

 

 

 

---

4 .문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class RGB {
    static int[][] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        dp = new int[n+1][4];
        for (int row = 1; row <= n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= 3; col++) dp[row][col] = Integer.parseInt(st.nextToken());
        }
        
        for (int i = 2; i <= n; i++) {
            dp[i][1] += Math.min(dp[i-1][2], dp[i-1][3]);
            dp[i][2] += Math.min(dp[i-1][1], dp[i-1][3]);
            dp[i][3] += Math.min(dp[i-1][1], dp[i-1][2]);
        }
        
        int min = 1000000000;
        for (int i = 1; i <= 3; i++)
            if(min > dp[n][i])    min = dp[n][i];
 
        System.out.println();
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= 3; col++) {
                System.out.print(dp[row][col] + " ");
            }
            System.out.println();
        }
        
        System.out.println(min);
        
        br.close();
    }
}
 

 

<정답 확인>

 

---

5. 느낀점 또는 개선 사항

- 아직 최댓값을 정의하는 과정이 쉽지만은 않은 것 같다.

→ 단계화해서 문제를 접근하는 것이 필요하다고 판단된다.