글 읽기 - 계단오르기 문제는 재귀로 풀수 없나요???

yeop9657 5년 전 0

시간초과가 발생하여서 혹시 해당 문제는 재귀로 불가능한가요?

아니면 제가 어느 부분을 잘 못하고 있는지 알 수있을까요?

감사합니다 :)

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

#define MAX_STEP 2

long long maxVal = 0;
vector<int> stepBy;

void step(long long sum, int index, int total, int privous) {

	if (total <= index) { 
		if (total == index && sum > maxVal) { maxVal = sum; return; }
		return;
	}

	if (privous >= MAX_STEP) { privous = 0; step(sum + stepBy.at(index), index + 2, total, privous);  }

	step(sum + stepBy.at(index), index + 1, total, privous + 1);
}

int main(void)
{
	int testcase = 0;
	cin >> testcase;

	for (int ii = 0; ii < testcase; ii++) {
		int value = 0;
		cin >> value;

		stepBy.push_back(value);
	}

	step(0, 0, testcase, 0);
	cout << maxVal << endl;
	return 0;
}

seico75 5년 전 0

재귀만으론 안되고 memoization 으로 이전결과를 저장해서 활용해야합니다

yeop9657 5년 전 0

;;; 어떻게 적용해야 할지 잘 모르겠는데 Sum을 전역으로 하고 처리하면 되는건가요?

jh05013 5년 전 0

다이나믹 프로그래밍에 대해 알아보세요.

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

문제

문제

출처

ICPC

계단오르기 문제는 재귀로 풀수 없나요???

yeop9657 5년 전 0

seico75 5년 전 0

yeop9657 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말