Cooper's devlog

RGB거리 : 1149번 - JAVA 본문

Algorithm/Baekjoon

RGB거리 : 1149번 - JAVA

cooper_dev 2020. 7. 16. 03:46

1. 문제 링크

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

 

1149번: RGB거리

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

www.acmicpc.net

 

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 .문제 풀이

 

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
34
35
36
37
38
39
40
41
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();
    }
}
 
 cs

 

<정답 확인>

 

5. 느낀점 또는 개선 사항

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

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

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

포도주 시식:2156번-JAVA  (0) 2020.07.16
스티커:9465번 - JAVA  (0) 2020.07.16
오르막수:11057번 - JAVA  (0) 2020.07.15
RGB거리 : 1149번 - JAVA  (0) 2020.07.15
1, 2, 3 더하기 3 : 15988 - JAVA  (0) 2020.07.13
'Algorithm/Baekjoon' Related Articles more
Comments