'정수삼각형'에 해당되는 글 1건

1932번 정수 삼각형



문제 해석


문제가 이해되셨나요?


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

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

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

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

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





3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

이런 식이네요.

그럼 아래로 내려오면서 가장 큰 값을 구해보겠습니다. 귀찮은데



7 

3
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));
	
}


반응형
블로그 이미지

REAKWON

와나진짜

,