글 읽기 - c언어 메모이제이션 / 시간초과

pcw 5년 전 0

Top - down 방식으로 코드를 작성했습니다.

메모이제이션을 위해 소스코드 중 표시한 부분을 추가했을 때 출력이 다르게 나오네요.. 코드 한 번 읽어주시면 감사하겠습니다.

메모이제이션 부분을 생략하고 작성하면 출력은 맞지만 시간초과됩니다..

(+) 이제 막 알고리즘을 배우기 시작하는 단계인데 동적 프로그래밍을 할 때 Top - down 방식과 Bottom - up 방식 중 어떤 것을 선호하시나요? Bottom - up 방식은 메모이제이션을 구현하지 않아도 되는 것 같아 앞으로는 조금 덜 신경쓸 수 있는(?) Bottom - up방식을 사용할까 고민중입니다..

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

int go(int n, int i);

int a[2][100001];
int d[100001];

int main()
{
	int n, t;
	scanf("%d", &t);

	while (t--)
	{
		scanf("%d", &n);
		for (int i = 0; i <= n; i++)	/*점수가 0점일 경우 d[n]에 0이 들어갈 수 있으므로*/
			d[i] = -1;					/*-1로 초기화*/

		for (int i = 0; i < n; i++)
			scanf("%d", &a[0][i]);
		for (int i = 0; i < n; i++)
			scanf("%d", &a[1][i]);

		printf("%d\n", max(go(n, 0), max(go(n, 1), go(n, 2))));
	}

	return 0;
}

int go(int n, int i)
{
	if (d[n]>0)					/*메모이제이션*/
		return d[n];

	if (n >= 0)
	{
		if (i == 0)
			d[n] = max(go(n - 1, 0), max(go(n - 1, 1), go(n - 1, 2)));
		else if (i == 1)
			d[n] = max(go(n - 1, 0), go(n - 1, 2)) + a[0][n];
		else if (i == 2)
			d[n] = max(go(n - 1, 0), go(n - 1, 1)) + a[1][n];


		return d[n];
	}
	return 0;

}

seico75 5년 전 1

go 함수의 입력은 두개인데 메모이제이션의 인자는 하나네요.

go 함수를 저렇게 만드신거는 두 변수가 정해져야 뒤의 답이 정해진다는 걸텐데..

d도 두 인자를 받게 만드면 어떨까요?

pcw 5년 전 0

seico75님 감사합니다.

같은 방식인데 d를 2차원 배열로 수정하고 제출해서 맞았습니다!

함수의 입력의 개수와 메모이제이션의 인자의 개수가 달라 틀렸던 건가요?

seico75 5년 전 1

제가 댓글을 늦게 확인을 했네요.

메모이제이션은 미리 저장된 값으로 (여러 단계 재귀가 들어가야할)처리를 대신해서 시간을 줄이는 방식입니다.

따라서 재귀처리의 조건(입력파라메터)와 메모이제이션의 입력이 같아야 한다고 저는 이해를 하고 있습니다.

이 경우에 현재 위치(n) 뿐 아니라 바로 전단계의 상태(i)에 따라서 처리되는 값이 다른데 오직 위치만을 보고

저장한 값을 쓰면 틀린 값을 쓰게 되는 것으로 보입니다.

pcw 5년 전 0

@seico75

넵 조언 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c언어 메모이제이션 / 시간초과

pcw 5년 전 0

seico75 5년 전 1

pcw 5년 전 0

seico75 5년 전 1

pcw 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말