[백준알고리즘-JAVA]1932번 풀이(정수 삼각형) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1932번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1932 (정수 삼각형)

문제

        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번째 줄까지 정수 삼각형이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

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

입력 예시

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

출력 예시

30

성공 코드

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

public class Main {

	static int N ;
	static Integer[][] arr;
	static Integer[][] dp;
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());;
		
		arr = new Integer[N][N];
		dp = new Integer[N][N];
		
		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j <= i ;j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		dp[0][0] = arr[0][0];
		
		for(int i = 0 ; i < N ; i++)
		max(N-1,i);
		
		int max_value = 0;
		for(int i = 0 ; i < N ;i++)
			max_value = Math.max(max_value, dp[N-1][i]);
		
		System.out.println(max_value);
}
	public static int max(int row, int col) {
		
		if(dp[row][col] == null) {
			if(col==0) {
				dp[row][col] = max(row-1,col) + arr[row][col];
			}
			else if(row==col) {
				dp[row][col] = max(row-1,col-1) + arr[row][col];
			}	
			else
				dp[row][col] = Math.max(max(row-1,col), max(row-1,col-1)) + arr[row][col];
		}
		
		return dp[row][col];
	}
}

정수 삼각형 알고리즘은 길이가 길어 보이지만 상당히 간단한 방법으로 해결할 수 있었습니다. 해당 문제에서의 핵심은 바로 어떠한 점화식을 이용하여 답을 도출할지입니다. 

 

수많은 DP문제들은 점화식만 잘 세운다면, 쉽게 풀이하실 수 있습니다. 점화식을 잘 세우기 위해서는 문제를 이해하고 쉽게 풀이하는 방법을 찾아야 합니다.

 

사실 이 방법을 찾는 게 핵심이자 가장 어려운 문제이죠... ㅎㅎ 일반적인 저희들은 이를 해결하기 위해 아주 간단한 방법이 있죠! 바로 많은 문제를 접하고 풀어보며, 기억하는 것입니다... ㅎㅎ 막일 파이팅..

---

알고리즘 흐름도

입력받기 -> dp [0][0] 초기화 하기 -> 반복하여 재귀 실행하기 -> 최댓값 출력하기

---

STEP1 문제 이해하기

문제를 살펴보면 피라미드 형식으로 입력을 받았다면, 가장 첫째 줄부터 시작하여 큰 수를 찾아 더하는 문제입니다. 그런데 여기서 조건은 대각선 왼쪽 또는 대각선 오른쪽이죠 이점을 꼭 기억해야 점화식을 쉽게 세울 수 있습니다. 위에서부터 왼쪽, 오른쪽 아래로 간다... 뭐 지금 수준에서는 음... 배열을 선언해서 그 앞 뒤 인덱스를 사용하면 될 거 같은데?라는 생각이 들긴 하네요 

 

이러한 생각을 가지고 다음 STEP으로 넘어가 보도록 하죠

---

STEP2 입력받기

 입력 예제를 살펴보면 그냥 입력을 첫 줄부터 차례로 입력받은 것을 볼 수 있습니다. 그렇다면, STEP1에서 생각했던 배열을 이용해 보도록 하겠습니다.

(배열 이외에도 컬렉션 및 제가 생각하지 못했던 방법이 있을 수 있습니다.)

 

		N = Integer.parseInt(br.readLine());;
		
		arr = new Integer[N][N];
		
		for(int i = 0 ; i < N ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j <= i ;j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}

일단은 2차원 배열로 입력받은 값을 저장합니다. 여기서 왜 INTEGER로 했냐 하면, INT로 하면 마지막 줄 외에는 빈 곳에 0이 들어가서 혹시나 나중에 재귀를 할 때 0 값과 빈 곳이라는 것을 표현하기 위해 INTEGER로 선언했습니다.

 

(INTEGER배열을 INT와 다르게 비어 있는 인덱스는 NULL이 Default값이 됩니다.)

 

이런 식으로 값을 지정해 줍니다. 다음으로 넘어가 봅시다.

---

STEP 3 재귀 점화식 이해하기 및 구현하기

 

 핵심입니다. 피라미드 형식으로 봤을 때는 어떻게 풀지 정확히 생각나지 않았지만, 입력 예시를 보는 순간  그냥 배열로 해결하면 되겠구나 하는 생각이 들었습니다. 일단 dp문제를 풀기 위해서, 값들의 최댓값을 저장할 수 있도록 dp배열을 하나 선언해 줍니다. (이 배열은 arr과 똑같은 형식으로 선언해 줍니다.)

 

그 후 dp [0][0]을 arr [0][0]으로 초기화해줍니다. (왜냐하면 첫 번째 줄에 있는 값의 최댓값은 항상 자기 자신일 수밖에 없지요)

 

그리고 저희는 방식을 선택해야 합니다. 어떠한 방식이냐! 바로 위에서부터 찾을 건지, 아래서 부터 찾을건지! 일명 top-down 또는 bottom-up 방식이라고도 불리죠

 

저는 top-down방식을 많이 사용해서 해당 방식대로 하기로 했죠. 그렇다면 max라는 재귀 함수를 만들어줍니다.

public static int max(int row, int col) {
		
		return dp[row][col];
	}

자 점화식을 세워봅시다. 우선 가장 기본적인 것 먼저! 우선 저는 top방식임으로 거꾸로 생각해 줘야 합니다. 아까 피라미드 형식에서 4 5 2 6 5에 있는 줄을 먼저 고려해 준다는 의미가 되죠. (쉽게 이해하기 위해서 dp는 해당 인덱스에서 가질 수 있는 최댓값을 의미합니다.)

 

그렇다면 마지막 줄에 있는 4에 있는 인덱스의 값은 무엇이 최대일 까요?

 

 - 네 올라올 수 있는 길이 하나밖에 없죠. 바로 윗줄의 2 이를 배열 형식으로 생각하면 행이 -1이고 열이 자신과 같은 곳이죠. 즉, 열=0 일 때는 바로 그 값을 더해주면 끝

 

public static int max(int row, int col) {
		
		if(dp[row][col] == null) {
			if(col==0) {
				dp[row][col] = max(row-1,col) + arr[row][col];
			}
		}
		
		return dp[row][col];
	}

arr [row][col]을 더해준 의미는 마지막으로 자기 자신의 값도 더해야 하니깐 그런 겁니다.

 

물론 앞선 if문의 의미는 해당 배열에 이미 값이 있다면, 한 번이라도 재귀가 돌아간 값이니 더 이상 재귀하지 말라! 즉, 메모이제이션을 활용하기 위한 조건문입니다.

 

다음 조건을 생각해보죠. 마지막 줄의 5는 올 수 있는 값이 그 전 줄인 2와 7 즉 이를 배열로 생각하면???

row-1/col과 row-1/col-1 중에 큰 값을 고르면 되겠죠? 

 

마지막 줄 5와 마찬가지로 2 6은 해당 값에 걸리게 되죠 일단 이것은 보류(왜냐하면 여러 값이 이런다? 마지막 else로 묶어줄 가능성이 잇기에 보류합니다.)

 

이와 같이 마짐가줄의 마지막 열 5는 row-1/ col-1의 값이 가지게 됩니다. 이를 코딩해 주면 이제 다음과 같죠.

public static int max(int row, int col) {
		
		if(dp[row][col] == null) {
			if(col==0) {
				dp[row][col] = max(row-1,col) + arr[row][col];
			}
			else if(row==col) {
				dp[row][col] = max(row-1,col-1) + arr[row][col];
			}	
			else
				dp[row][col] = Math.max(max(row-1,col), max(row-1,col-1)) + arr[row][col];
		}
		
		return dp[row][col];
	}

이제 고민할 것은 어떻게 인자로 row와 col를 넘겨줄지!

 

이는 사실 간단하죠. 저희가 넘겨줄 row은 마지막 줄을 넘겨주면 됩니다. 그러면 알아서 재귀로 그 이전 row들은 찾아주기 때문이죠 (top-down방식) 그럼 col은 무엇을 넘겨주어야 될까요? 모든 열을 넘겨줘야 됩니다...!!

 

왜냐하면 마지막 줄은 모든 열을 채운 수이기 때문이죠! 이를 main함수에서 구현해 준다면

for(int i = 0 ; i < N ; i++)
		max(N-1,i);

이런 식으로 max함수를 호출해 준다면 dp에는 각 열의 최댓값들이 나열되어 있습니다.

---

 

STEP 4 최댓값 출력하기

사실 뭐.. 최댓값 출력은 굉장히 쉽습니다.

		int max_value = 0;
		for(int i = 0 ; i < N ;i++)
			max_value = Math.max(max_value, dp[N-1][i

설명할 것도 그다지 없기에 Math.max함수를 이용해서 최대 값을 비교하면서, 가장 큰 값을 넣어주어 max_value를 출력하면 끝입니다.