공부 자료/알고리즘
(C/C++) 백준 1932번 - 정수 삼각형
뚜루뚜루세니
2021. 8. 2. 10:29
728x90
문제출처: https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
1. 코드
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int tri[501][501]; //각 위치의 값
int dp[501][501] = { 0, }; // 그 위치로 갔을 때 합
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) { //tri 배열에 입력받기
for (int j = 1; j <= i; j++) {
scanf("%d", &tri[i][j]);
}
}
dp[1][1] = tri[1][1];
for (int i = 2; i <= n; i++) {
for(int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + tri[i][j];
//합이 치대가 되기 위해서, 윗줄에서
//왼쪽이나 오른쪽 중 큰 것 선택
}
}
int Max = 0;
for (int i = 1; i <= n; i++) {
if (Max < dp[n][i])
Max = dp[n][i];
}
printf("%d", Max);
}
|
cs |
2. 해결과정
합이 최대가 되는 경로에 있는 수의 합을 출력.
2차원 배열로 각각 삼각형에 들어가는 값(tri)와, 그 위치로 갔을 때 숫자들의 합(dp)를 설정해준다.
합이 최대가 되어야하므로 윗줄에서 아랫줄을 선택할 때, 왼쪽과 오른쪽 중 큰 것을 선택해줘야한다.
따라서 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j] 라는 점화식을 도출해낼 수 있다.
3. 느낀점
dp 문제는 처음 풀어봐서 어려웠다. 점화식을 도출해내는 것 자체가 어려웠던 문제
728x90