[동적계획법 DP] 백준 온라인 저지 (BOJ) 1932번 정수 삼각형 풀이

1932번 정수 삼각형

문제 해석

---

문제가 이해되셨나요?

맨 위 삼각형 꼭지점에 있는 숫자부터 시작해서 아래까지 계속하여 더합니다. 그 중 가장 큰 수를 구하는 것입니다. 

하지만 조건이 걸려있지요! 바로 위에서 아래로 내려올때 대각선 왼쪽, 또는 오른쪽으로 내려오면서 그 숫자를 더하는 겁니다. 

문제에 있는 예제부터 보겠습니다.

아참, 정삼각형으로 표현하기보다는 직삼각형으로 표현했어요, 그게 편하거든요. 그러면 조건이 왼쪽, 오른쪽으로 내려오는 게 아닌 바로 밑의 수를 더하거나 대각선 오른쪽을 더하면 문제의 조건과 동일하게 됩니다. 

그렇다면 2차원배열로 구현하기가 편합니다.

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

이렇게 더하면 합이 30으로 이보다 큰 수를 계산할 수 없습니다. 이해가 가셨는지요?

제약 조건

---

주어지는 n은 1이상 500 이하, 수는 0이상 9999이하입니다.

무식하게 하나하나씩 더하게 된다면 시간초과를 먹게 되겠네요.

모든 수를 9999이상으로 500개를 더하면 최대 500만 이하의 값을 갖게 되니까 int형 변수면 충분합니다.

풀이

---

 

7

3 8

이렇게 놓고 보면 문제를 풀어보면 10과 15라는 결과를 얻을 수 있습니다. 그렇다면 답은 15입니다.

7

3 8

8 1 0

이것은 어떻게 계산할 수 있을까요? 그 전에 계산했던 값으로 답을 낼 수 있습니다.

이 삼각형을 다음과 같이 쪼개보겠어요?

8     

1 0  

아래의 오른쪽 삼각형 A와

3

8 1

아래 부분의 왼쪽 삼각형 B로 쪼갰습니다. 그렇다면 A에 대한 답은 9, B에 대한 답은 11이라는 것을 알 수 있습니다.

전체삼각형은 

7

A B

로 압축이 될 수 있겠네요.

그렇다면 답을 계속 구해보지요

7과 A를 더하면 16, 7과 B를 더하면 18로 답은 18이라는 것을 알 수 있습니다.

더 큰 삼각형에 대해서도 이와 같은 노가다를 하다보면 예제의 답을 직접 구할 수 있을 겁니다. 예제 문제의 결과를 표로 나타내보았습니다. 아래에서부터 시작해서 위의 방법으로 계산하게 된다면 30이라는 답을 얻어 낼 수 있을 겁니다.

30
23	21
20	13	10
7	12	10	10
4	5	2	6	5

이것을 이제 코드로 나타내야합니다.

int solve(int y, int x)라는 함수는 위치 y, x에서 시작해서 규칙대로 내려가, 가장 큰 수를 반환하는 함수입니다. 만약 solve(2, 2)라면 배열 [2][2]에서 시작해서 가장 큰 값을 반환하게 됩니다. 우리가 원하는 답은 solve(1, 1)이 되겠습니다. 왜냐면 (1,1)에서 출발해서 가장 큰 값이 우리가 원하는 답이니까요. 그렇나요? solve는 밑으로 내려가면서 바로 아래의 수를 더한 값과 대각선 오른쪽의 수를 더한 값을 비교해 가장 큰 수를 반환합니다. 그렇다면 max(현재 그 점의 수 + solve(y+1, x), solve(y+1, x+1))로 재귀호출할 수 있습니다.

기저사례는 y나 x가 n보다 클 때의 조건입니다.

 

전체 코드는 아래와 같습니다.

#include <stdio.h>
#include <string.h>
#define N 501
#define max(a,b) a>b ? a:b

int triangle[N][N], dp[N][N];
int n;
int solve(int y, int x) {
	if (y>n || x>n ) return -99999999;
	if (y == n) return triangle[y][x];
	if (dp[y][x] != -1) return dp[y][x];
	int ret = 0;
	ret = max(triangle[y][x] + solve(y + 1, x),
		triangle[y][x] + solve(y + 1, x + 1));
	return dp[y][x] = ret;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &triangle[i][j]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(1, 1));
	
}