백준 1932 - 정수 삼각형 JAVA

문제, 입/출력조건, 테스트케이스

해당 문제는 DP(다이나믹 프로그래밍) 문제다.

보자마자 대략 어떤 식으로 풀면되겠다라고 생각이 든 문제였다.

 

(해당 문제 접근과정)
1. subset 느낌으로 dfs로 코드를 짜봄 
2. 점화식을 도출해서 DP로 바꿔봄
3. Scanner를 써서 시간이 좀 오래걸리는 것을 보고 BufferedReader로 재구현

글 보다 코드를 보는 게 더 편한 우리는 개발자이므로 DFS 소스코드와 DP소스코드 작성해 보았습니다.

 

1. DFS로 코드를 짠 경우

package boj;

import java.util.Scanner;

public class Boj_1932 {
	static int dp[][], N, max;
		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new int[N][N];
		max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = i ; j >= 0; j--) {
				dp[i][j] = sc.nextInt();
			}
		}
		
		dfs(0, 0, 0);
		System.out.println(max);
	}

	private static void dfs(int i, int j, int total) {
		if(i == N) { 
        //배열의 마지막 행까지 다 돌아봤다면 이전 최댓값과 현재 값 비교하여 최댓값 갱신
			max = Math.max(total, max);
			return;
		}
		// 각 두 노드 방문하는 경우를 dfs
		dfs(i+1, j, total+ dp[i][j]); 
		dfs(i+1, j+1,total+ dp[i][j]);
	}
}

2. DP로 코드를 짠 경우

package boj;

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

public class Boj_1932 {
	static int arr[][], dp[][], N, max;
		
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		dp = new int[N][N];
		max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = i ; j >= 0; j--) {
				arr[i][j] = Integer.parseInt(stz.nextToken());
				if(i == N-1) { // 마지막 행의 배열의 경우에는 dp에서 점화식의 첫값으로 활용함
					dp[i][j] = arr[i][j];
				}
			}
		}
		
		// 배열의 마지막행 - 1번째부터 돌면서 각각 max값을 dp 배열에 저장함
		for (int i = N-2; i >= 0; i--) {
			for (int j = 0; j <= i; j++) {
				dp[i][j] = arr[i][j]+Math.max(dp[i+1][j], dp[i+1][j+1]);
			}
		}
		//제일 꼭대기인(0,0)배열에는 최댓값이 저장되어 있으므로 출력 후 종료		
		System.out.println(dp[0][0]);
	}

}

 

 

총평

1. DP문제를 계속 풀다보니 손으로 끄적여보고(메모) 중요한 건 규칙성 찾고 점화식 만들기라는 걸 깨달았다.
2. 점화식을 찾은 후 바로 메모이제이션 구현하는 게 익숙치 않다면
브루트포스 -> DFS -> DP 순으로 구현하면서 감을 찾는 게 좋을 것 같다는 생각을 하였다.
3. DP는 결국 문제를 많이 풀어보는 수밖에 없다는 것을 깨달았다.