글 읽기 - 어디가 잘못된건가요??

asterisk120 5년 전 0

첨부한 소스코드에서 점화식은

An = A(n-1)과 A(n-2)중 큰 것 + a(n) (an은 n번째 계단의 값, An은 문제 조건에 맞는 경우 중 가장 큰 수 입니다)

이렇게 짰어요

recursion(score,index,step)은 A(index)입니다

recursion 요청이 들어왔을때 만약 메모된 것이 있으면 반환하고

그렇지 않은 경우는 step을 따져서

step이 2일 경우 (이전에 밞은 계단이 현재 계단과 이웃한 경우)

다음 recursion을 호출할때 index를 한칸 뛰어서(2) 호출하고

그렇지 않은경우 현재 index - 1 까지의 최선 합, index - 2 까지의 최선 합을 비교하고 index위치의 원소를 더해서 반환하도록 짰는데

논리가 잘못된건가요 짜는걸 잘못짠건가요??

반례는

10 12 15 100 20 15 10

v v v v v

해서 답 : 152 입니다

디버깅을 아무리해봐도 모르겠습니다... 도움 부탁드립니다..

#include <iostream>

constexpr int MAX = 301;

int memo[MAX];

inline int Max(int a, int b) {
	if (a > b) return a;
	else return b;
}

int recursion(int score[], int index, int step) {
	if (index < 1)
		return 0;
	if (memo[index])
		return memo[index];
	else
		if (step == 2)
			return memo[index] = recursion(score, index - 2, 1) + score[index];
		else
			return memo[index] = Max(recursion(score, index - 1, step + 1), recursion(score, index - 2, 1)) + score[index];
}

int main(void)
{
	int n, score[MAX] = {};

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &score[i]);
	printf("%d", recursion(score, n, 1));
}

memo[index]는 "index번째 계단을 밟을 때까지의 최대 점수"입니다. 그런데 이 값은 "이전의 계단을 밟은 상태"인가요, "이전 이전의 계단을 밟은 상태"인가요? 두 상태에 따라서 답이 달라질 수 있어야 하는데, 처음 호출 시 step=1로 호출을 받아 "이전의 계단을 밟은 상태"에서의 답을 구해 memo해놓고서는, 나중에 step=2로 호출을 받았으면 "이전 이전의 계단을 밟은 상태"에서의 답을 구해야 하는데 그러지 않고 memo에 있던 값을 그대로 돌려주니, 답이 어긋나게 됩니다. 그 반대의 경우도 마찬가지입니다.

그래서 메모이제이션을 할 때 step=1인 경우와 step=2인 경우는 별개의 경우로 분리해서 구해야 합니다.

asterisk120 5년 전 0

매번 답변해주셔서 감사합니다!!

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

문제

문제

출처

ICPC

어디가 잘못된건가요??

asterisk120 5년 전 0

djm03178 5년 전 1

asterisk120 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말