늘 겸손하게

백준 1932 - 정수 삼각형 (C++) 본문

코딩 문제/백준

백준 1932 - 정수 삼각형 (C++)

besforyou999 2021. 8. 16. 14:52

 

 

DP 문제를 처음으로 스스로 풀었네요

 

문제 풀이

 

모든 경우를 다 구하려면 시간 초과가 나오므로 dynamic programming으로 풀어야 한다.

 

1. 합이 최대가 되는 경로에 있는 수의 합을 출력해야 하고, 위에서 아래로 내려갈 때 더 큰 숫자가 있는 방향으로 나아가야 하므로 두 개의 숫자를 비교한 후 더 값이 큰 숫자를 반환하는 함수를 만들어두자.

 

2. 삼각형의 맨 위에서 아래로 내려가는데, 더 큰 수가 있는 방향으로 내려가고 더 큰 수를 합하면서 맨 아래까지 내려가야 한다.

-> 이 과정에서 지금까지 합한 값을 기록해야 하고 다음 값을 계산할 때 기록한 값을 사용한다.

 

3. edge case 주의 : 맨 오른쪽 정수는 바로 윗줄의 맨 오른쪽, 맨 왼쪽 정수는 바로 윗줄의 맨 왼쪽만 선택 가능하다.

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
 
using namespace std;
 
int mat[501][501];
int dp[501][501];
 
int get_max(int a, int b) { // a ,b 비교 후 값이 더 큰 숫자 반환
    if ( a > b) return a;
 
    return b;
}
 
int main (void) {

    // 입력
int n;
    cin >> n;
    int max =0;
    for (int i = 1; i <= n ; i++ )
        for (int j = 1 ; j <= i ; j++ )
            cin >> mat[i][j];
 
    dp[1][1] = mat[1][1];
   
    for (int i = 2 ; i <= n ; i++) {
        for (int j = 1; j <= i ; j++ ) {
            if ( j == i ) //맨 오른쪽 정수
                dp[i][j] = ( dp[i-1][j-1] + mat[i][j]);
            else if ( j == 1 ) //맨 왼쪽 정수
                dp[i][j] = ( dp[i-1][j] + mat[i][j]);
            else // 왼쪽, 오른쪽 중 더 큰 숫자 선택
                dp[i][j] = get_max(dp[i-1][j-1],dp[i-1][j]) + mat[i][j];
        }
    }

// 모든 경로 중, 최종합이 가장 큰 경로 선택
    for (int i = 1 ; i <= n ; i++ )
        if ( max < dp[n][i] ) max = dp[n][i];
 
    cout << max << endl;
 
    return 0;
}
 
 
 cs
 
 
  

 

'코딩 문제 > 백준' 카테고리의 다른 글

백준 11660 - 구간 합 구하기 5  (0) 2021.08.30
문제 11054 가장 긴 바이토닉 부분 수열 ( C++ )  (0) 2021.08.20
백준 1158 요세푸스 문제 ( C++ )  (0) 2021.08.11
백준 18870 ( C++ )  (0) 2021.08.10
백준 3273 ( C++ )  (0) 2021.07.24
'코딩 문제/백준' Related Articles more