문제
풀이
삼각형의 꼭대기에서부터 아래층으로 내려옵니다. 내려오면서 선택 된 수들의 합이 최대인 경로를 구하는 문제입니다.
저는 재귀함수를 통해 구현했습니다.
재귀 함수 안에서 현재 위치의 아래와 대각선 오른쪽의 재귀함수를 호출하여 두 값중 더 큰 값을 메모이제이션 해줬습니다. 다음은 구현한 재귀함수입니다.
1
2
3
4
5
6
7
8
9
10
11
int path(int y, int x)
{
// 기저 사례
if (y == n - 1)
return triangle[y][x];
// 메모이제이션
int &ret = cache[y][x];
if (ret != -1)
return ret;
return ret = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x];
}
가장 아래층에서는 그냥 자신의 수를 return하며 기저사례를 처리해줬습니다.
소스 코드
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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int triangle[500][500];
int cache[500][500];
int n;
int path(int y, int x)
{
// 기저 사례
if (y == n - 1)
return triangle[y][x];
// 메모이제이션
int &ret = cache[y][x];
if (ret != -1)
return ret;
return ret = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < i + 1; j++)
scanf("%d", &triangle[i][j]);
memset(cache, -1, sizeof(cache));
printf("%d\n", path(0, 0));
return 0;
}
