Algorithm, boj, 1932(정수 삼각형), dp

DP(다이나믹 프로그래밍)

• 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
• dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
  

  해결하지 못한 원인

• dp문제는 겹치는 문제가 발생한다. 즉, 앞에서 누적된 결과로 현재 문제가 풀리기 때문에 누적된 것을 어떻게 활용하고 쉽게 수식으로 풀 수 있을지 생각해보자.
• 문제를 쉽게 도식화해서 생각해보자 ㅠ

  문제 풀이

• 양쪽 끝의 최고합은 고정
  
  • if(j==1) list[i][1] = list[i][1] + list[i-1][1];
  • if(i==j) list[i][j] = list[i][j] + list[i-1][j-1];
• 양쪽 끝이 아니라면 두 부모중 더 큰 값을 선택
  • list[i][j] = list[i][j] + Math.max(list[i-1][j-1], list[i-1][j])

 package org.baekjoon;

import java.util.Scanner;

public class test1932 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		  Scanner sc = new Scanner(System.in);

		  int n = sc.nextInt();
		  int[][] list = new int[n+1][n+1];
		  int max = 0;
		  for (int i=1; i<=n; i++) {
			  for (int j=1; j<=i; j++) {
				  list[i][j] = sc.nextInt();

				  // 1. 왼쪽 대각선
				  if(j==1) list[i][1] = list[i][1] + list[i-1][1];
				  // 2. 오른쪽 대각선
				  else if(i==j) list[i][j] = list[i][j] + list[i-1][j-1];
				  // 3. 대각선이 아니라면 부모중에 큰값과 더한다.
				  else
					  list[i][j] = list[i][j] + Math.max(list[i-1][j-1], list[i-1][j]);

				  if (list[i][j] > max)
					  max = list[i][j];
			  }
		  }
		  System.out.println(max);
	}
}

---

Reference

문제바로가기 문제풀이