BOJ 1932번 : 정수 삼각형

문제의 입력이 정수들을 삼각형 형태로 받는 모양이라 2차원 배열로 받으려 했으나, 500층을 생각 하면, 맨 윗층은 정수가 1개 인데 500개의 int형 메모리를 할당하기 아까워서 1차원 배열로 해결해 보려 했으나... 너무 코드만 길어지기에 처음 생각했던 방식으로 해결 하였다.

 

맨 위의 3층만 예시로 살펴보자.

맨 위에부터 0층, 1층, 2층 이라고 하면, 각 층의 가장 왼쪽 정수는 윗층의 가장 왼쪽 정수만 더할 수 있고, 가장 오른쪽 정수 또한 윗 층의 가장 오른쪽 정수만 더 할 수 있다. 나머지 정수들은 윗층의 두 수에서 좀 더 큰 수만을 선택하면 된다. "층"을 표현하기 위해서는 이차원 배열이 가장 쉬워 사용하였다.

 

이 것을 점화식을 표현하면,

 

if(j==0) : dp[i][j] += dp[i-1][j]

if(j==i) : dp[i][j] += dp[i-1][j-1]

else : dp[i][j] += MAX(dp[i - 1][j - 1], dp[i - 1][j])

이다.

 

<소스코드>

#include<iostream>
#include<vector>
using namespace std;
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
 
int main() {
    int t;
    int _max;
    cin >> t;
    int dp[501][501] = { 0, };
    for (int i = 0; i < t; i++) {
        if (i == 0) {
            cin >> dp[0][0];
            _max = dp[0][0];
        }
        else {
            for (int j = 0; j <= i; j++) {
                cin >> dp[i][j];
                if (j == 0) 
                    dp[i][j] += dp[i - 1][j];
                else if (j == i) 
                    dp[i][j] += dp[i - 1][j-1];
                else 
                    dp[i][j] += MAX(dp[i - 1][j - 1], dp[i - 1][j]);
                if (_max < dp[i][j])
                    _max = dp[i][j];
            }
        }
    }
    cout << _max << endl;
}

 

문제 :

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

1932번: 정수 삼각형