글 읽기 - 이런 방식으로는 풀수 없을까요?

yeop9657 5년 전 0

하나의 계단에서 부터 차례로 +1, +2 가는 경우 모두 보는데 틀리는 경우가 있네요.

어디가 문제일까요?

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

#define PAIR pair<int, bool>

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

	vector<int> stairs = vector<int>(step, 0);
	vector<PAIR> answer = vector<PAIR>(step, make_pair(0, true));
	for (int ii = 0; ii < step; ii++) { cin >> stairs[ii]; }

	int length = step - 1;
	answer[length].first = stairs.back();

	for (int ii = length; ii >= 0; ii--) {

		int nx = ii - 1, ny = ii - 2;

		if (answer[ii].second) {
			answer[nx].first = max(answer[nx].first, answer[ii].first + stairs[nx]);
			answer[nx].second = false;
		}
		else if (ny > 0) {
			answer[ny].first = max(answer[ny].first, answer[ii].first + stairs[ny]);
			answer[ny].second = true;
			continue;
		}

		if (ny < 0) { continue; }
		answer[ny].first = max(answer[ny].first, answer[ii].first + stairs[ny]);
		answer[ny].second = true;
	}

	cout << answer.front().first << endl;

	return 0;
}

yeop9657 5년 전 0

+1 계단으로 오는 경우에는 answer[ny].second = true로 +2 계단으로 오는 경우에는 answer[ny].second = false로 처리하고 있어요.

luniro 5년 전 0

23-25번째 줄 answer[nx].first와 answer[ii].first + stairs[nx]중에서 answer[nx].first가 클 때 answer[nx].second = false로 처리하면서 오류가 생길 수 있어요

answer[ii].first + stairs[nx]가 클 때만 처리하거나 하는 식으로 바꾸셔야 할 것 같습니다

이렇게 입력하면 ii == 4일 때 answer[3].front == 45, answer[2].front == 135가 되고, ii == 3에서 answer[2].first (==135) > answer[3].first + stairs[2] (==60)이라 계단이 5, 4, 2가 더해지므로 answer[2].second == true여야 하는데 false가 되면서 오답이 됩니다

정답: 155

출력: 145

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

문제

문제

출처

ICPC

이런 방식으로는 풀수 없을까요?

yeop9657 5년 전 0

luniro 5년 전 0

yeop9657 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말