백준 1932번 : 정수 삼각형

문제 출처

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

1932번: 정수 삼각형

 

문제 설명을 읽고 트리를 사용해서 푸는건가? 싶었는데 자세히 보면 트리는 아니라는걸 알 수 있다.

입력을 배열로 받아야 할거 같았다.

2차원 배열로 생각을 했는데 <아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.> 이 부분을 열번호를 i라고 했을 때 다음 행의 i 또는 i+1을 더할 수 있다고 가정했다.

 

재귀를 사용할때마다 시간초과 당한 트라우마가 있어 재귀를 사용하지말까 하다가 일단 문제 파악을 위해서 재귀로 도전

#include<stdio.h>
#define MAX 500
int num[MAX][MAX];
int sum(int n, int flo, int pos)
{
	int sum1, sum2;
	if (n - 1 == flo) return num[flo][pos];
	sum1 = sum(n, flo + 1, pos);
	sum2 = sum(n, flo + 1, pos + 1);

	if (sum1 > sum2) return sum1 + num[flo][pos];
	else return sum2 + num[flo][pos];

}
int main()
{
	int n;
	int i, j;
	int ans;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			scanf("%d", &num[i][j]);
		}
	}

	ans = sum(n, 0, 0);

	printf("%d\n", ans);
}

비주얼 스튜디오에서 예제는 맞게 나왔는데 역시나 시간초과가 발생했다.

시간을 줄이는 가장 쉬운 방법은 중복계산이 발생하는 부분을 없애는거라고 생각하는데

그 부분을 찾아보겠다.

예제의 문제를 들어보면 내가 짠 코드 대로 계산하는 게

7+3+8+2+4

7+3+8+2+5

7+3+8+7+5

7+3+8+7+2

7+3+1+7+5

7+3+1+7+2

7+3+1+4+2

7+3+1+4+6

.

.

.

이런식으로 이어지는데 아주 일부인 이것만 적어봐도 중복 계산이 발생하는걸 알 수 있다.

그래서 중복계산 값을 적어주는 배열을 하나 더 만들었다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 500
int num[MAX][MAX];
int memo[MAX][MAX] = {0};
int sum(int n, int flo, int pos)
{
	int sum1, sum2;
	if (n - 1 == flo) return num[flo][pos];

	if (memo[flo + 1][pos] == 0)
		memo[flo + 1][pos] = sum(n, flo + 1, pos);
	if (memo[flo + 1][pos + 1] == 0)
		memo[flo + 1][pos + 1] = sum(n, flo + 1, pos + 1);

	sum1 = memo[flo + 1][pos];
	sum2 = memo[flo + 1][pos + 1];

	if (sum1 > sum2) return sum1 + num[flo][pos];
	else return sum2 + num[flo][pos];

}
int main()
{
	int n;
	int i, j;
	int ans;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			scanf("%d", &num[i][j]);
		}
	}

	ans = sum(n, 0, 0);

	printf("%d\n", ans);
}