Cooper's devlog

정수 삼각형: 1932번 - JAVA 본문

Algorithm/Baekjoon

정수 삼각형: 1932번 - JAVA

cooper_dev 2020. 7. 16. 22:27

1. 문제 링크

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

 

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�

www.acmicpc.net

2. 문제 설명

3. 문제 접근

1) arr[][]를 선언

1 7        
2 3 8      
3 8 1 0    
4 2 7 4 4  
5 5 6 2 6 5

 

 

2) 구조를 살펴보도록 하자.

1 7        
2 3 8      
3 8 1 0    
4 2 7 4 4  
5 5 6 2 6 5

 

-arr[3][2]합의 최대값 = arr[2][1]까지의 합 혹은 arr[2][2]까지 합의 최대값 + arr[3][2]

 

3) 해당 식을 점화식으로 표현

- dp[row][col] = Math.max(dp[row-1][col-1],dp[row-1][col]) + arr[row][col]; (dp[][] : 최대 값을 담는 배열)

- bottom-up 방식으로 문제를 접근한다.

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
42
43
44
package dp1_practice;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class integer_triangle {
    static int arr[][];
    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());
        int max = 0;
        arr = new int[n+1][n+1];
        dp = new int[n+1][n+1];
        
        for (int row = 1; row <= n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= row; col++) {
                arr[row][col] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp[1][1] = arr[1][1];
        if(n > 1) {
            for (int row = 2; row <= n; row++) {
                for (int col = 1; col <= row; col++) {
                    dp[row][col] = Math.max(dp[row-1][col-1], dp[row-1][col]) + arr[row][col];
                }
            }
        }
        
        for (int col = 1; col <= n; col++) {
            if(max < dp[n][col])    max = dp[n][col];
        }
        
        System.out.println(max);
        
        br.close();
    }
}
 
  
 

<정답 확인>

5. 느낀점

-어렵지 않은 규칙성을 발견하는 문제라 부담이 되지 않는 선에서 문제를 해결할 수 있었다.

 

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

동물원: 1309번 - JAVA  (0) 2020.07.17
쉬운 계단 수 : 10844번 - JAVA  (0) 2020.07.17
포도주 시식:2156번-JAVA  (0) 2020.07.16
스티커:9465번 - JAVA  (0) 2020.07.16
RGB거리 : 1149번 - JAVA  (0) 2020.07.16
'Algorithm/Baekjoon' Related Articles more
Comments