[백준 1932][C++] 정수 삼각형 (Silver 1)

[문제보기]

 1932. 정수 삼각형

1932번: 정수 삼각형

 

[풀이과정]

각 층의 양 끝점으로 올 수 있는 경우는 위 층의 양 끝점에서 내려오는 경우밖에 없다. 

그리고 중간에 있는 점들은 위 층에서 양 쪽 대각선에 위치하고 있는 점에서 내려오는 두 가지 경우가 있다.

그렇게 때문에 필자는

왼쪽 끝 점에 대한 식, dp[i][1] = dp[i-1][1] + map[i][1];

오른쪽 끝 점에 대한 식, dp[i][i] = dp[i-1][i-1] + map[i][i];

중간 점에 대한 식, dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + map[i][j];

형식으로 세웠다.

 

[소스코드]

#include <iostream>
using namespace std;
int map[501][501] = {0};
int dp[501][501] = {0};

int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            cin >> map[i][j];
        }
    }

    dp[1][1] = map[1][1];
    for(int i=2; i<=n; i++){
        for(int j=1; j<=i; j++){
            if(j == 1){
                dp[i][j] = dp[i-1][j] + map[i][j];
            }
            else if(j == i){
                dp[i][j] = dp[i-1][j-1] + map[i][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + map[i][j];
            }
        }
    }

    int Max = 0;
    for(int i=1; i<=n; i++){
        Max = max(Max, dp[n][i]);
    }

    cout << Max;
}

 

[해결 과정 중 실수한 부분]

양 끝점에 대한 식을 하나의 조건으로 묶어 하나의 식으로 나타냈었다. 그러나 틀렸다고 나와, 다시 생각해보니

층이 내려갈수록 오른쪽 끝점에 대한 크기가 하나씩 증가하기 때문에 -1을 해줘야 한다