Beakjoon 1932 정수 삼각형

15 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1932

나의 풀이

DP[i][j] = i번째 층 j번째 인덱스에서 구할 수 있는 합의 최댓값

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

위 그림과 같은 삼각형이 있을 때 이를 배열로 표현하면

i\j	0	1	2	3	4
0	7
1	3
2	8	1	0
3	2	7	4	4
4	4	5	2	6	5

다음과 같이 표현할 수 있고 이 배열을 map[i][j]라고 하겠다.
이 때 DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + map[i][j] 인 것을 알 수 있다.
단 j-1 < 0 이면 DP[i-1][j-1] 구할 수 없고, j = i 일 때 DP[i-1][j]도 구할 수 없기 때문에 각각의 예외처리를 해줘야 한다.

풀이 코드 : 1932 정수 삼각형

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int DP[500][500];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    vector<vector<int>> map;
    cin>>n;
    map.resize(n);
    for(int i=0;i<n;i++){
        map[i].resize(i+1);
        for(int j=0;j<=i;j++){
            cin>>map[i][j];
        }
    }

    DP[0][0] = map[0][0];

    for(int i=1;i<n;i++){
        for(int j=0;j<=i;j++){
            if(j-1 >= 0){
                DP[i][j] = DP[i-1][j-1];
            }
            if(j != i){
                DP[i][j] = max(DP[i][j], DP[i-1][j]);
            }
            DP[i][j] += map[i][j];
        }
    }

    int answer = 0;
    for(int i=0;i<n;i++){
        if(answer < DP[n-1][i]) answer = DP[n-1][i];
    }
    cout<<answer;
}

채점결과