[백준] 1932 : 정수삼각형

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

1932번: 정수 삼각형

문제 분석

 

마치 트리로 이루어진 것과 같은 삼각형을 첫째 줄부터 마지막 줄까지(위->아래) 이동하며 최대 합을 구하는 문제이다.

 

3번째 줄의 1 원소를 보면, 7-3-1=11의 합이 만들어지는 경우와 7-8-1=16 합이 만들어지는 경우가 있다.

합이 최대가 되도록 만들어야하기때문에 3과 8 중 값이 3인 원소를 골라야한다.

즉, 크기가 큰 원소를 선택하는 것이 아닌(그리디가 아닌) 현재까지의 합을 기준으로 원소를 선택해야한다.(완전탐색)

 

현재 위치의 최대합을 구하기 위해서 이전 줄의 최대합을 이용하여 비교하기 때문에 dp를 사용한다.

dp[i][j] = (i, j) 위치에서의 최대합

 

코드

#include <bits/stdc++.h>
using namespace std;
int tri[504][504], dp[504][504];
int n, answer;

int main(){
    //1. 입력받기
    cin >> n;
    for (int i=0;i<n;i++){
        for(int j=0;j<i+1;j++){
            cin >> tri[i][j];
        }
    }
    //2. 합 구하기
    dp[0][0]= tri[0][0];
    for (int i=1;i<n;i++){
        for (int j=0;j<=i;j++){ 
            if (j==0) dp[i][j] = tri[i][j] + dp[i-1][j];
            else dp[i][j] = tri[i][j] + max(dp[i-1][j-1], dp[i-1][j]);
        }
    }
    //3. 가장 큰 합 구하기
    for (int i=0;i<n;i++){
        if (answer<dp[n-1][i]) answer = dp[n-1][i];
    }
    //4. 정답 출력
    cout << answer;
}

 

개선 부분 + 여담

 

삼각형을 첫째 줄부터 맨 아래 줄까지 도달하여 구한 최대 합은 맨 아래에서부터 첫째 줄까지 도달하여 구한 최대 합과 같다.

 

현재 코드에서는 위->아래로 각각의 위치에서 누적 합(=최대 합)을 구했는데, 이럴 경우 누적 합을 구하기 위해 마지막 줄의 원소들을 처음부터 끝까지 순회하며 가장 큰 값을 가진 원소를 구해야한다.

 

만약 아래->위로 이동한다면, 최대합은 맨 위의 원소 dp[0][0]에 존재할 것이다.

 

개선된 코드

#include <bits/stdc++.h>
using namespace std;
int tri[504][504];
int n, answer;

int main(){
    //1. 입력받기
    cin >> n;
    for (int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cin >> tri[i][j];
        }
    }
    //2. 합 구하기
    for (int i=n-2;i>=0;i--){
        for (int j=0;j<=i;j++){ 
            tri[i][j] = tri[i][j] + max(tri[i+1][j], tri[i+1][j+1]);
        }
    }
    //3. 정답 출력하기
    cout << tri[0][0];
}