글 읽기 - 값을 기록하는 배열을 2차원으로 만들어야 하나요??

rktkek456 5년 전 0

마지막 계단을 무조건 밟아야 하기때문에 위에서 아래로 내려오는 방식으로 작성했습니다.

그런데

7
10 12 15 100 20 15 10
정답 : 152

같은 중간에 큰 값이 들어갈 경우에 전혀 대응을 못하네요...

메모이제이션에 들어가는 값이 뒤에 있는 계단부터 계산 되어서

10 25 35 125 140 137 150 로 답이 150으로 출력됩니다.

네번째 값이 10 + 20 + 100 = 130이 되어야 하는건 알겠는데 어떤 부분을 고쳐야 할 지 도저히 감이 안잡힙니다...ㅠㅠ

어떤걸 수정해야 할까요?ㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int jumpOneStep(const int& maxScoreVal, const int& scoresVal, int& jumpMemory) {
	if (jumpMemory == 2) {
		jumpMemory = 0;
		return -987654321;
	}

	jumpMemory += 1;
	return maxScoreVal + scoresVal;
}

int jumpTwoStep(const int& maxScoreVal, const int& scoresVal) {
	return maxScoreVal + scoresVal;
}

int getMaxScore(const vector<int>& scores) {
	vector<int> maxScore(scores.size(), 0);
	if (scores.size() == 1) {
		return scores[0];
	}
	else if (scores.size() == 2) {
		return scores[0] + scores[1];
	}
	else if (scores.size() == 3) {
		return max(scores[0] + scores[2], scores[1] + scores[2]);
	}

	int vecSize = maxScore.size() - 1;
	maxScore[0] = scores[vecSize];
	maxScore[1] = scores[vecSize] + scores[vecSize - 1];
	maxScore[2] = max(scores[vecSize] + scores[vecSize - 2], scores[vecSize - 1] + scores[vecSize - 2]);

	int jumpMemory;
	if (scores[vecSize] + scores[vecSize - 2] < scores[vecSize - 1] + scores[vecSize - 2]) {
		jumpMemory = 2;
	}
	else {
		jumpMemory = 1;
	}

	for (int i = 3; i < scores.size(); ++i) {
		int oneStepJumpScore = jumpOneStep(maxScore[i - 1], scores[vecSize - i], jumpMemory);
		int twoStepJumpScore = jumpTwoStep(maxScore[i - 2], scores[vecSize - i]);

		if (oneStepJumpScore < twoStepJumpScore) {
			jumpMemory = 1;
			maxScore[i] = twoStepJumpScore;
		}
		else {
			maxScore[i] = oneStepJumpScore;
		}
	}

	/*
	for (auto i : maxScore)
		cout << i << " ";
	cout << endl;
	*/
	return maxScore[vecSize];

}

int main() {
	int numberOfStair;
	vector<int> scores;
	cin >> numberOfStair;
	for (int i = 0; i < numberOfStair; ++i) {
		int score;
		cin >> score;
		scores.push_back(score);
	}
	cout << getMaxScore(scores);
}

huyng1233 5년 전 0

네 2차원배열을 통해서 마지막 계단으로 올때, 1번 뛰었는지 2번 뛰었는지를 체크하시는 것이 좋습니다

srand 5년 전 0

1차원으로도 될껄요?

D[i] = max ( D[i-2] + A[i], D[i-3] + A[i-1] + A[i] ) for i in 3..N

D[i] = A[i] for i in 1, 2

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

문제

문제

출처

ICPC

값을 기록하는 배열을 2차원으로 만들어야 하나요??

rktkek456 5년 전 0

huyng1233 5년 전 0

srand 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말