백준 1932 정수 삼각형

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

1932번: 정수 삼각형

 

 

 

EXPLANATION

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

삼각형 맨 위에서 부터 바로 양옆에 대각선으로 한칸씩 내려가면서 숫자를 더할 때, 가장 밑에서 구해지는 값들 중 최댓값을 구하는 문제이다.

 

 

예제 입력

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

위와 같이 입력값이 주어지면 아래와 같이 arr[i][j]에 담는다.

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

arr[i][j]를 선언할 때 모두 0으로 초기화시킨 후 입력값을 arr에 담는다.

그러면 입력값이 담아지지 않은 arr[i][j]의 값으 그대로 0이다.

 

dp[i][j]를 따로 선언하지 않고 그냥 arr[i][j]에 dp값들을 갱신하겠다.

그러면

arr[i][j] = max( arr[i][j], arr[i][j - 1]) + arr[i][j]

가 된다. ( 즉, dp[i][j] = max( dp[i][j], dp[i][j - 1]) + arr[i][j] )

 

그런데 예외가 있다. j = 0 이면 arr[i][j - 1]의  값이 없으므로

if(j == 0) arr[i][j] = arr[i-1][0] + arr[i][0];

 

또, i = 0이면 arr[i - 1][j]의 값도 없는데 arr[0][0]은 base이기 때문에 그대로 두면 된다. ( dp[0][0] = arr[0][0] ) 

 

 

위처럼 arr[i][j]를 갱신하면서 맨 밑(i == N - 1) 단계 까지 왔을 때,

arr[N - 1][j]를 dp값으로 갱신시키면서 동시에 이전 최댓값과 비교하고 더 크면 최댓값을 갱신하면서

arr[N - 1][j] 값 들 중에서 최댓값을 찾으면 된다.

 

 

 

i\j	0	1	2	3	4
0	7	0	0	0	0
1	10	15	0	0	0
2	18	16	15	0	0
3	20	25	20	19	0
4	24	30	27	26	24

 

 

 

CODE

#include <iostream>
using namespace std;

int arr[500][500] = {};
int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0 ; j <= i; j++){
            cin>> arr[i][j];
        }
    }
    
    int maxValue = 0;
    for(int i = 0; i <N ; i++){
        for(int j = 0; j <= i; j++){
            if(i == 0) {}   //i = 0일 때, arr[i][j] 그대로 두면 되니까 애초에 i = 1부터 시작하도록 둬도 된다. 주의할 점은, 그렇게 하면 N = 1일 때 maxValue를 이 for 문 안에서 구현이 안되기 때문에 for문 위에서 maxValue = arr[0][0]로 작성하는 걸 잊으면 안된다.
            else if (j == 0) {
                arr[i][j] = arr[i-1][0] + arr[i][0];
            } else {
                arr[i][j] = max(arr[i-1][j], arr[i-1][j-1]) + arr[i][j];
            }
            if(i == N - 1) maxValue = max(maxValue, arr[i][j]);    //맨 밑 단계오면 최댓값 찾기 
        }
    }
    cout << maxValue << "\n";
}