백준 1149번 RGB거리 자바 Java (☆공부 274일차)

1149 RGB거리

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

1149번: RGB거리

 

 

 

 

---

백준 1149번 문제 RGB거리

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	96395	52194	38876	53.427%

문제

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

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

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

입력

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

출력

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

제한

 

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

예제 입력 2

3
1 100 100
100 1 100
100 100 1

예제 출력 2

3

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3

102

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

208

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

힌트

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/260

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

4달 전에 푼 문제

 

 

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

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

 

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

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

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n][3];
        
        // 첫 번째 미리 넣기
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 3; i++) {
            dp[0][i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int[] now = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + now[0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + now[1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + now[2];
        }
        
        System.out.println(Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2])));
        br.close();
        
    }
}
 

 

 

 

---

저번이 더 효율적이다