BOJ 1932 정수삼각형

1. 구현로직

   1. dp를 사용

   2. 어떤 블로그 풀이 글에서 누적 값, 그리고 RGB 방식과 비슷하다는 hint를 얻었다

      (*) 틀린 이유는 for문에서 등호, 범위 설정을 잘못 해줬다

      

실제로 해당 삼각형의 누적된 모습을 노트에 그려보면 1번 열에 속한 값들은 모두 이전의 행값 + 자신의 값이라는 것을 알 수 있다. 예를 들어 2층부터 3의 자리에 누적될 값은 같은 열이면서 이전행의 값인 7+ 자신의 값 3으로 10이 되는 것이다.

참고 블로그 : https://fbtmdwhd33.tistory.com/49

​

1. 코드

   package baekjoon.Silver;
      
   import java.io.BufferedReader;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
      
   public class BOJ_1932_정수삼각형 {
      
   	public static void main(String[] args) throws Exception {
   		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   		int N = Integer.parseInt(br.readLine());
   		int[][] numArr = new int[N][N];
   		int[][] dp = new int[N][N];
      
   		// 입력
   		numArr[0][0] = Integer.parseInt(br.readLine().trim());
   		for (int i = 1; i < N; i++) {
   			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
   			for (int j = 0; j < i + 1; j++) {
   				numArr[i][j] = Integer.parseInt(st.nextToken());
   			}
   		}
      
   		dp[0][0] = numArr[0][0];
   		for (int i = 1; i < N; i++) {
   			for (int j = 0; j <= i; j++) {
   				if (j == 0) {
   					dp[i][j] = dp[i - 1][j] + numArr[i][j];
   				} else if (j > 0 && j < i) {
   					dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + numArr[i][j];
   				} else {
   					dp[i][j] = dp[i - 1][j - 1] + numArr[i][j];
   				}
   			}
   		}
      
   		int answer = Integer.MIN_VALUE;
   		for (int i = 0; i < N; i++) {
   			answer = Math.max(answer, dp[N - 1][i]);
   		}
   		System.out.println(answer);
   	} // end of main
   }
      
   

2. 느낀점

   • 이번 문제는 오래걸렸지만 비슷한 dp문제를 풀어보면서 빨리 푸는 연습, 그리고 시간재고 푸는 연습을 해야겠다

3. 꿀팁!

   • 질문검색에서 반례를 찾다가 이 문제에 해당하는 좋은 반례 모음이 있어서 링크 공유함

     7가지 반례 모음 : http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb1/index.html

문제 링크 : 백준 1932 정수삼각형