반응형

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

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

간단한 점화식을 만들어서 푸는 문제였습니다.

 

1. arr배열에 각 수들의 입력을 받습니다.

 

2. 점화식을 세워 메모이제이션을 통해 최댓값을 저장합니다.

 

3. 마지막 줄의 메모이제이션 된 수들 중 가장 큰 수를 출력합니다.

 

위의 2번에서 세운 점화식은 다음과 같습니다.

 

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

 

[ 소스 코드 ]

 

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
#include<iostream>
 
using namespace std;
 
int n;
int arr[500][500];
int dp[500][500];
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dp[0][0] = arr[0][0];
 
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + arr[i][0];
    }
 
    int ans = dp[n - 1][0];
 
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
        }
    }
 
    for (int i = 1; i < n; i++) {
        ans = max(ans, dp[n - 1][i]);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08

+ Recent posts

티스토리툴바