[C++] 백준 1932 - 정수 삼각형

백준 1932 정수 삼각형

난이도 : 실버 1

시간 : 20분 소요

 

 

문제

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

풀이 과정

 

먼저 arr라는 2차원 배열을 만들어서 삼각형 구조의 입력값을 받았다.

그 후 dp라는 2차원 배열을 만들어서 N번째 배열에서 각각의 최댓값을 저장했다.

dp[i][j]는 i번째 줄에서 j항을 선택했을 때의 최대가 되는 경로의 합을 의미한다.

 

	7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

예를 들면, dp[1][1]은 1번째 1번 항을 선택했을 때의 최댓값이다. 따라서 dp[1][1] = 7 ( arr[1][1] )

 

dp[2][1]은 2번째 1번 항을 선택했을 때의 최댓값이다. 경우의 수가 7+3만 가능하기 때문에

dp[2][1] = 10( dp[1][1]+arr[2][1] )

 

같은 원리로 dp[2][2] = 15( dp[1][1] + arr[2][2] )

 

3번째부터 경우의 수가 생긴다.

dp[3][1]은 7+3+8만 가능하기 때문에 dp[3][1] = 18( dp[2][1] + arr[3][1] )

하지만 dp[3][2]는 dp[2][1] + arr[3][2] 또는 dp[2][2] + arr[3][2] 둘 다 가능하다.

그래서 dp[2][1] 과 dp[2][2] 중에 더 큰 값을 확인하여 arr[3][2]를 더한 값을 dp[3][2]에 저장해야 한다.

 

수식으로 나타내면 다음과 같다.

 dp[i][j] = Max(dp[i-1][j], dp[i-1][j-1]) + b[i][j];

 

최종 코드

#include <iostream>
#include <vector>

using namespace::std;

int b[501][501];
int dp[501][501];
int N;

int Max(int a, int b){
    return a>b ? a : b;
}

int main(){
    scanf("%d", &N);
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=i; j++){
            cin>>b[i][j];
        }
    }
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=i; j++){
            dp[i][j] = Max(dp[i-1][j], dp[i-1][j-1]) + b[i][j];
        }
    }
    int r = 0;
    for(int i=1; i<=N; i++){
        if(r<dp[N][i]){
            r = dp[N][i];
        }
    }
    
    printf("%d\n", r);
}

 

잡담

이틀 동안 dp 때문에 고생을 좀 했었다.

dp는 작은 문제를 해결함으로써 전체를 아우르는 하나의 점화식을 만들어야 하는데

그 부분이 나에게는 어려웠다.

 

하지만 dp문제도 계속 풀다보니 어느 정도 요령이 생겼고, 이번 문제는 빠르게 풀 수 있었다.

자신감 갖고 더 열심히 해야겠다.