백준 1932. 정수 삼각형 (JAVA)

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

public class Main {
	
	static int[][] arr;
	static int[][] dp;
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		 arr = new int[n][n];
		 dp = new int[n][n];
		
		for(int i = 0 ; i < n ; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			for(int j = 0 ; j < i + 1; j++ ) {
				
				arr[i][j] = Integer.parseInt(st.nextToken());
				
			}
		}
		
		for(int i = 0 ; i < n ;i++) {
			for(int j =0; j < n ;j++) {
				dp[i][j] = -1;
			}
		}
		for(int i = 0 ; i < n ; i++) {
			dp[n - 1][i] = arr[n - 1][i];
		}
		
		System.out.println(search(0,0));
	}
	
	static int search(int depth, int index) {
		
		if(depth == n -1) return arr[depth][index];
		
		if(dp[depth][index] == -1) {
			dp[depth][index] = Math.max(search(depth + 1,index), search(depth + 1,index + 1)) + arr[depth][index];
		}
		
		return dp[depth][index];
	}
}

○ 문제 요약

삼각형 제일 위층에서 아래층까지 내려올 때 값을 합해서 나올 수 있는 최댓값을 출력해라.

○ 문제 풀이

처음에 위에서부터 최댓값만 찾는 경로로 값을 구했는데 전혀 엉뚱한 값이 나와서 수작업으로 계산을 해봤더니 이 방법으로 가면 안 된다는 것을 알았다.... 그래서 고민하다가 결국 해결하지 못하고 도움을 요청했다. 그랬더니 그 방법으로는 절대 값을 구할 수 없다고 한다. 그래서 밑에서부터 올라가서 값을 구해야 하기 때문에 코드를 싹 다 뒤엎었다. 

 

먼저 입력받을 삼각형의 층 수만큼 arr와 dp를 생성했다. 그리고 arr에 입력받은 값을 하나씩 입력했고, int 타입으로 dp를 만들었기 때문에 값을 비교하기 위해 -1로 초기화해주었다. 우리는 여기서 문제를 해결하는 과정을 밑에서 위로 올라가야 하기 때문에 제일 아래층에 먼저 데이터를 넣어주고 값을 비교해 더 큰 값을 넣을 것이다. 이해하기 쉽게 그림으로 보자.

search(0,0)을 실행하면

if( 0 != 4) >> 조건 불충족

 

if( dp[0][0] == -1 ){  >> 처음에 dp를 -1로 초기화해주었기 때문에 조건 성립

 dp[0][0] = Math.max(search(1,0),search(1,1)) + arr[0][0]; >> 재귀로 search(1,0)과 search(1,1)을 실행

}

계속 재귀 함수를 통해서 depth가 n - 1과 같을 때까지 도달하면 dp[n - 1][index] = arr[n - 1][index]로 넣어준 값이 반환되면서 값을 비교해서 큰 값을 현재 arr[depth][index] 값과 더해서 dp[depth][index]에 넣어준다. 

 

호출된 재귀 함수만큼 위 과정을 실행하면 dp[0][0]에 값이 입력되고 최종적으로 최댓값을 출력하게 된다.

○ 결과