[백준] 1932: 정수 삼각형 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

정수 삼각형의 그림은 삼각형의 형태를 하고 있지만, 보면 n 번 째 줄에는 n 개의 정수가 있는 것을 알 수 있다.

코드의 형태로 나타내면 다음과 같다.

arr = [

[1],

[2, 3],

[4, 5, 6],

[7, 8, 9, 10],

[11, 12, 13, 14, 15]

]

 

 

DP를 이용해 더한 값을 dp 배열에 추가하는 방식으로 할 예정이다.

먼저 값이 들어가있지 않은 dp 배열을 똑같이 준비해 준다.

 

그리고 그림을 그려보면 다음 두 식을 산출해 낼 수 있다.

dp[n][j] = dp[n - 1][j] + arr[n][j];

dp[n][j + 1] = dp[n - 1][j] + arr[n][j + 1];

 

근데 계산을 하는데 곂치는 부분이 있다. 바로 두번째 점화식은 다음 반복문인 n이 ++ 되면 dp[n][j] 자리에 간다.

정수 삼각형으로 생각해 보아도 같다. 두 번째 줄에서 2와 4를 더하고 2와 5를 더한다. 그리고 3과 5를 더하고 3과 6을 더한다. 여기서는 5가 곂친다.

그럼 2와 5를 더한 것과, 3과 5를 더한 것 중에서 더 높은 값을 저장해야 한다. Math.max() 메서드를 통해서 가능하기에 이 부분은 넘어간다.

 

 

여기서 중요한 건 예외사항이다. 여기서 예외사항은 첫 번째 요소와 마지막 요소이다. 다른 요소들은 모두 두 번씩 중복 계산이 되지만, 이 두 요소는 한 번만 계산이 된다. 이 부분은 조금만 생각해 보면 예외이지만 예외가 아니다. 등호 하나로 해결 가능하다.

 

두 번째 for 문을 한 번만 덜 돌면 된다.

 

 

 

  풀이

 

 

package src.dp;

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

public class IntegerTree {




    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


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

        int[][] arr = new int[502][502];
        int[][] dp = new int[502][502];


        for(int i = 1; i <= n; i++){

            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 1; j <= i; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }

        }

        int maxVelue = 0;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){

                if(j == i && j != 1) break;

                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + arr[i][j]);
                dp[i][j + 1] = dp[i - 1][j] + arr[i][j + 1];

                int compare1 = dp[i][j];
                int compare2 = dp[i][j + 1];

                if(compare1 > maxVelue || compare2 > maxVelue){
                    maxVelue = Math.max(compare1, compare2);
                }



            }
        }

        System.out.println(maxVelue);



    }

}