[백준/C++] 1932번: 정수 삼각형(S1)

문제

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

1932번: 정수 삼각형

 

 

사용한 알고리즘

2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP)

 

 

풀이 

1. 크기 n*(n+1)/2인 num배열과 dp배열을 만들어준다.

2. num[idx]에는 각 수를 담고
   dp[idx]에는 해당 위치까지 오는 경로 중 선택된 수의 합의 최댓값을 담을 것이다.

3. i(=level)과 j로 이중 for문을 돌면서 idx++을 해주어 원소 하나하나 접근한다.

4. i=1(맨 위)일 때는 dp[idx]=num[idx], 
   j=1(맨 왼쪽)일 때는 dp[idx]=dp[idx-i+1]+num[idx],
   j=i(맨 오른쪽)일 때는 dp[idx]=dp[idx-i]+num[idx] 이다.

  중간에 껴있는 수들은 
  dp[idx]=max(dp[왼쪽부모의 인덱스], dp[오른쪽 부모의 인덱스])+num[idx] 인데
  왼/오른쪽 부모의 인덱스는 각각 idx-i와 idx-i+1이다.

5. 마지막 줄 (i=n)일 때의 dp값 중 max값을 출력해준다.

     

 

소스코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin>>n;
    /*
     1. 크기 n*(n+1)/2인 num배열과 dp배열을 만들어준다.
     2. num[idx]에는 각 수를 담고
        dp[idx]에는 해당 위치까지 오는 경로 중 선택된 수의 합의 최대값을 담을 것이다.
    */
    int num[n*(n+1)/2], dp[n*(n+1)/2];
    int idx=0,ans=0;

    // 3. i(=level)과 j로 이중for문을 돌면서 idx++을 해주어 원소 하나하나 접근한다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            cin >>num[idx];
            if(i==1){ // 맨 위
                dp[idx]=num[idx];
            }
            else if(j==1){ // 맨 왼쪽
                dp[idx]=dp[idx-i+1]+num[idx];
            }
            else if(j==i){ // 맨 오른쪽
                dp[idx]=dp[idx-i]+num[idx];
            }
            else{ // 중간에 껴있는 수
                dp[idx]=max(dp[idx-i],dp[idx-i+1])+num[idx];
            }
            // 5. 마지막 줄 (i=n)일때의 dp값중 max값을 출력해준다.
            if(i==n) ans=max(ans,dp[idx]);

            idx++;
        }
    }
    cout<<ans;
    return 0;
}