Cooper's devlog

RGB거리 : 1149번 - JAVA 본문

Algorithm/Baekjoon

RGB거리 : 1149번 - JAVA

cooper_dev 2020. 7. 15. 01:30

1. 문제 링크

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

 

1149번: RGB거리

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

www.acmicpc.net

 

2. 문제 설명

3. 문제 접근

예제 입력1

기본 입력 값

26 40 83
49 60 57
13 89 99

 

(1)첫번 째와 해당 위치와 비교했을 때, 값이 최소가 되는 값을 dp[][]에 값을 넣는다.

(문제 조건  : i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. -> 앞뒤의 열 숫자가 겹치면 안된다)

 

1) dp[2][1] = Math.min(dp[1][2], dp[1][3]) = (89, 132) -> 89

2) dp[2][2] = Math.min(dp[1][1], dp[1][3]) = (86, 143) -> 86

2) dp[2][3] = Math.min(dp[1][1], dp[1][2]) = (83, 97) -> 83

  R G B
1 26 40 83
2 89 86 83
3 13 89 99

 

 

(2) (1)번 작업을 반복한다.

 

1) dp[3][1] = Math.min(dp[3][2], dp[3][3]) = (99, 96) -> 89

2) dp[3][2] = Math.min(dp[3][1], dp[3][3]) = (176, 172) -> 172

2) dp[3][3] = Math.min(dp[3][1], dp[3][2]) = (188, 185) -> 185

  R G B
1 26 40 83
2 89 86 83
3 96 172 185

 

 

(3) n번째 해당하는 값의 최소값을 찾는다.

  R G B
1 26 40 83
2 89 86 83
3 96(정답!) 172 185

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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(min);
        
        br.close();
    }
}
 
  

 

<정답 확인>

5. 결론

-증말 재귀함수는 건드릴 수가 없다;; -> 일단 bottom-up부터

'Algorithm > Baekjoon' 카테고리의 다른 글

RGB거리 : 1149번 - JAVA  (0) 2020.07.16
오르막수:11057번 - JAVA  (0) 2020.07.15
1, 2, 3 더하기 3 : 15988 - JAVA  (0) 2020.07.13
합분해 : 2225번 - JAVA  (0) 2020.07.13
덱 :10866번 - JAVA  (0) 2020.07.10
'Algorithm/Baekjoon' Related Articles more
Comments