[백준-1932번 자바/java] 정수 삼각형 _디버깅의 눈물

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

1932번: 정수 삼각형

 

 

 

정수 삼각형 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

68308

38680

29083

58.883%

문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

30

 

 

 

---

 

 

 

 

체크 포인트

1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법) 이용

-큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다.

 

n=5인 경우의 map[n][n] 배열 예시

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

 

위와 같이 크기가 5인 삼각형을 예로 볼 때, 

(1)삼각형의 값을 map[n][n] 배열에 입력해주고,

 

    	// 삼각형 최하단 행의 값을 dp배열로 동일하게 입력
    	for(int i=0; i<n; i++){
    		dp[n-1][i] = map[n-1][i];
    	}

 

(2)삼각형 맨 마지막 줄의 값(4 5 2 6 5)를 dp배열의 동일 위치에 입력해준다.

(3)이후 (0,0)인 7부터 아래 방향으로 재귀함수를 이용해 탐색을 하며 합을 구해나간다.

 

n=5인 경우 dp[n][n]의 예시

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

 

(4)dp배열에는 가장 아래서(4 5 2 6 5)부터 위 방향으로 합의 최대값을 구한다.

(5)합의 최대값은

 

(왼쪽 아래값 or오른쪽 아래값 중에서 큰 숫자) + 현재 위치의 숫자값이다.

 

 

 

예를 들어 4번째 줄 첫번째 값인 7은,

왼쪽 아래값 4와 오른쪽 아래값 5 중에서 더 큰 값인 5와

기존 map배열의 값 2를 더해 7을 입력한 것이다.

 

같은 방식으로 4번째 줄 두번째 값 12는,

왼쪽 아래값 5와 오른쪽 아래값 2 중에서 더 큰 값인 5와

기존 map 배열의 값 7을 더해 12를 입력했다.

 

                       map[n][n]                        dp[n][n]

                            7                              30
                          3   8                         23    21
                        8   1   0          ->         20   13   10
                      2   7   4   4                 7   12   10   10
                    4   5   2   6   5             4   5    2    6    5

 

 

2.삼각형 값을 map 배열에 입력받을 때 반복문의 조건 확인 (j<i+1)

 

    	// map 배열 내 값 입력
    	for(int i=0; i<n; i++){
    		st = new StringTokenizer(br.readLine(), " ");
    		// j<i+1
    		for(int j=0; j<i+1; j++){
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	// 삼각형의 크기
	static int n;
	// 삼각형 내 숫자를 담는 배열
	static int[][] map;
	// 다이나믹 프로그래밍 배열
	static int[][] dp;
	
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 삼각형의 크기
    	n = Integer.parseInt(st.nextToken());
    	
    	// 배열 초기화
    	map = new int[n][n];
    	dp = new int[n][n];
    	
    	// map 배열 내 값 입력
    	for(int i=0; i<n; i++){
    		st = new StringTokenizer(br.readLine(), " ");
    		// j<i+1
    		for(int j=0; j<i+1; j++){
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	// -1로 dp 배열 기본값 초기화
    	for(int i=0; i<n; i++){
    		for(int j=0; j<n; j++){
    			dp[i][j] = -1;
    		}
    	}
    	
    	// 삼각형 최하단 행의 값을 dp배열로 동일하게 입력
    	for(int i=0; i<n; i++){
    		dp[n-1][i] = map[n-1][i];
    	}
    	
    	System.out.println(solution(0,0));
    	
    } // end of Main
    
    
    
    
    static int solution(int depth, int x) {
    
    	// 마지막 행까지 탐색했다면,
    	if(depth==n-1){
    		// 해당 값 return
    		return dp[depth][x];
    	}
    	
    	// 해당 위치를 방문한 적이 없다면, 
    	if(dp[depth][x]==-1){
    		// dp[depth][x]는 (왼쪽 아래값과 오른쪽 아래 값 중에서 더 큰 수) + (현재 위치의 수)이다.
    		dp[depth][x] = Math.max(solution(depth+1, x), solution(depth+1, x+1)) + map[depth][x];
    	}
    	
    	
    	return dp[depth][x];
    } // end of solution

} // end of Main