글 읽기 - 어디가 잘못 되었는지 모르겠습니다... 출력값은 맞게 나오는것 같은

chrisjc 7년 전 0

재귀와 DP를 이용하여 구현하였는데

계속하여 실패가 나옵니다.

반례나 이유를좀 알려주세요 ㅠㅠ

그리고 질문드리고 싶은게 46번째 줄에

if (cnt == 3)
return -500;

이런 것을 좀더 깔끔하게 하는 방법이 있을까요?? 3번연속 밞게 되면 안된다는 것을 표현하고 싶은데..

재귀함수에서는 어떤식으로 표현할지 몰라서 저렇게 작은값을 주면 최대값 선정할때 피할 수 있으니까 항상 저런식으로 값을 넣어주는데

미로찾기문제나 다른 문제를 풀때도 저 구간을 저런식으로 작성하였는데 좋은 방법이 있을까요??

또한가지 다른 사람의 코드는 어떻게 볼 수 있나요??

감사합니다.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int stair[300];
int cache[300];

int max(int x, int y);
void solve();
int jump(int step,int cnt);

// 최고층수
int n = 0;

int main() {

	
	for (int i = 0; i < 300; i++)
	{
		cache[i] = -1;
	}

	cin >> n;

	if (!((n >= 1) && (n <= 300)))
		return 0;

	for (int i = 0; i < n; i++)
	{
		cin >> stair[i];

		if (!(1 <= stair[i]) && (stair[i]<=10000))
			return 0;
	}

	solve();

}


int jump(int currentstair, int step, int cnt)
{
	if (cnt == 3)
		return -500;

	if ((currentstair)== n)
	{
		return stair[n - 1];
	}
	
	if (cache[currentstair-1] != -1)
	{
		return cache[currentstair-1];
	}


	if ((currentstair) > n )
	{
		//선택하지 않는 방법이 뭐가 있을까???
		return -500;
	}


	int maxscore = 0;
	int score;
		 score = stair[currentstair-1];



	for (int i = 1; i < 3; i++)
	{
		if(i == 1)
		{
			cnt = cnt + 1;
			maxscore = max(maxscore, score + jump(currentstair+i, i, cnt));
		}
		else
		{
			cnt = 1;
			maxscore = max(maxscore, score + jump(currentstair+i, i, cnt));
		}
	}


	cache[currentstair-1] = maxscore;
		return cache[currentstair-1];



}

int max(int x, int y)
{
	if (x >= y)
		return x;
	else
		return y;
}

void solve()
{
	int maxvalue = 0;
	
	int cnt = 1;
	for (int i = 1; i < 3; i++)
	{
		maxvalue = max(maxvalue,jump(0+i, i, cnt));
	}


	cout << maxvalue << endl;

}

chrisjc 7년 전 0

해결 하였습니다.

캐쉬를 한개만 쓰는것이 아닌 이전 계단을 밞았는지 유무에 따라 2개를 만들어줘서 썼습니다.

왜냐하면 이전 계단을 밞지 않은 것을 캐쉬에 업데이트 한 후에 그 값을 사용하게 된다면 그 바로전 계단에서 그 값을 사용할 경우에는 연속해서 3가지 계단을

밞는 오류를 범하게 됩니다. 캐쉬를 두가지 사용하니까 AC가 뜹니다.

아직까지 리턴값을 음수로 줘서 해결하는 방법은 모르겠네요....

아시는분은 댓글 부탁드리겠습니다.

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

문제

문제

출처

ICPC

어디가 잘못 되었는지 모르겠습니다... 출력값은 맞게 나오는것 같은

chrisjc 7년 전 0

chrisjc 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말