공부 134일차: 백준 1149번 RGB거리 자바 java

1149 RGB거리

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

1149번: RGB거리

 

 

 

 

---

백준 1149번 문제 RGB거리

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

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

이렇게 적혀 있는 문제의 조건은 복잡해 보이지만, 결국 앞에 선택한 색과 다르기만 하면 된다는 말이다

 

따라서 지금 n번째 수에서 R, G, B를 선택했을 때 나오는 수를 모두 구해두고,

마지막에 빨강, 초록, 파랑 중 가장 작은 수를 출력하면 된다

 

 

---

정답 인정 코드

---

 

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n][3]; // 0: R, 1: G, 2: B
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 디버깅 System.out.println(Arrays.deepToString(dp));
        
        for(int i = 1; i < n; i++) {
            // 빨강일 땐 그전 색깔이 초록/파랑 중 작은 값에 더함
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + dp[i][0];
            // 초록일 땐 그전 색깔이 빨강/파랑 중 작은 값에 더함
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + dp[i][1];
            // 파랑일 땐 그전 색깔이 빨강/초록 중 작은 값에 더함
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + dp[i][2];
        }
        
        System.out.println(Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2])));
    }
 
}
 

 

마지막에서 dp[n-1]인 이유는 0부터 n까지 넣었기 때문에, n은 n-1 인덱스에 들어가 있기 때문이다

 

 

 

---