글 읽기 - 몇몇 케이스에서 정상적으로 동작하지 않는데 어떤 부분을 고쳐야 할까요...

rktkek456 6년 전 0

샘플 케이스에서는 정상적으로 동작하는데

예를 들어

40 30 20 10 1

이렇게 입력을 넣으면 81이 나와야 하는데 61이 나옵니다.

접근 방법은 꼭대기 계단을 무조건 밟아야 하기 때문에 꼭대기 부터 시작했습니다.

가장 높은 계단을 밟은 뒤 다음에 2칸 내려갈지 1칸 내려갈지 선택을 하고

1칸을 내려갔을 경우 이미 2칸을 연속으로 밟았기 때문에 무조건 그 다음은 2칸을 내려가야하고.

2칸을 내려갔을 경우 제약이 없기 때문에 1칸 또는 2칸 모두 선택 할 수 있게 코드를 짰습니다.

예를 들어서
계단을 밟고 있는 상태에서 1칸을 내려가면 2칸을 연속으로 밟았기 때문에
1칸을 내려가면 그 다음은 무조건 2칸을 내려가야 하고,

다음에 2칸을 내려가면 제약이 없기 때문에 1칸 혹은 2칸을 내려갈수 있다고 생각합니다.

어떤 부분을 고쳐야 할까요...ㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> step, cache;
int testCase;
decltype(auto) setFunc(int N) {
	testCase = N;
	step = vector<int>(N, 0);
	cache = vector<int>(N, -1);
	for (int i = 0; i < testCase; ++i)
		cin >> step[i];
}

int findMaxSum(int level, int jumpSize = -1) {
	//step[level]
	if (level == 0)
		return step[0];
	else if (level < 0) {
	//첫번째 계단을 넘어가면 0 반환
		cache[0] = 0;
		return 0;
	}
	
	int* ret;
	if (level == testCase)
		ret = &cache[level - 1];
	else
		ret = &cache[level];

	if (*ret != -1)
		return *ret;

	if (testCase == level)	//가장 높은 계단 부터 시작
		return *ret = max(findMaxSum(level - 2, 1), findMaxSum(level - 3, 2)) + step[level - 1];
	
	if (jumpSize == 2)
		return *ret = max(findMaxSum(level - 1, 1), findMaxSum(level - 2, 2)) + step[level];
	else if (jumpSize == 1)
		return *ret = findMaxSum(level - 2, 2) + step[level];
}

 int main() {
	 int N;
	 cin >> N;
	 setFunc(N);
	 findMaxSum(N);
	 cout << cache[N - 1];
}

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

문제

문제

출처

ICPC

몇몇 케이스에서 정상적으로 동작하지 않는데 어떤 부분을 고쳐야 할까요...

rktkek456 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말