[알고리즘] 백준 1932 JAVA 자바 동적프로그래밍

 

public class BaekJoon_16_1932 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[][] tree = new int[501][501];
		int[][] dp = new int[501][501];

		StringTokenizer st;
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j = 1; j <= i; j++) {
				tree[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = tree[i][j] + Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
			}
		}

		int max = dp[n][1];
		for (int i = 2; i <= n; i++) {
			if (max < dp[n][i])
				max = dp[n][i];
		}

		System.out.println(max + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

간단한 DP문제라 크게 할말은 없지만 조금 느낀점을 붙이자면 .. 이차원 배열을 만들때 n+1 이런식으로 만드는 것 보다 그냥 주어진 최대크기로 만들고 사용하는게 나은 것 같다.. 뭔가 예외적인 상황도 고려해야되고 난감해질 때도 있는듯. 

물론 해결책은 다 있겠지만..

 

이문제의 핵심은 [1][1] 부터 시작하는것이다. [0][0]부터 시작하면 잡다한 코드가 생긴다. [1][1]로 시작하면 i줄에 첫빠따를 시작할때 부모 노드중에서 가장 큰걸 집어넣어야하는데 여기서 [i-1][0]과 [i-1][1] 중 가장 큰 값을 넣으면 그걸 더해넣기만 하면 된다. 당연히 [i-1][0]의 값은 0이니까 가장큰값은 [i-1][1]이다.

 

근데 여기서 만약 음수가 추가되고 조건이 달라지면 말이 조금 달라지겠지만 어차피 그때도 그냥 Integer.MIN_VALUE를 초기화하고 비교하면 된다.

 

 

 

억지로 짧은 코드보다 이쁜 코드를 작성하려고 노력하는데, 사람마다 기준이 달라서 결국 사람을 많이 만나봐야하는 것 같다. Stream API도 얼른 공부해봐야지.