글 읽기 - 반례를 찾을 수 없습니다.. ㅠㅠ

mintflavoredwater 1년 전 0

게시판에 있는 모든 반례를 긁어모아도 걸리는 게 없고 저 로직이 왜 안먹히는 지도 이해할 수 없습니다.. 한 수 가르쳐주십시오

#include <iostream>
#include <vector>

int main() {
	int n;
	std::cin >> n;
	std::vector<int> scores(n + 1, 0);
	std::vector<std::pair<int, int>> cache(n + 1, std::make_pair(0, 0));

	for (int i = 0; i < n; ++i)
		std::cin >> scores[i + 1];

	if (n == 1) {
		std::cout << scores[1];
		return 0;
	}

	cache[1].first = scores[1];
	cache[2].first = cache[1].first + scores[2];
	cache[2].second = scores[2];

	for (int i = 3; i <= n; ++i) {
		cache[i].first = cache[i - 1].second + scores[i];
		cache[i].second = cache[i - 2].first + scores[i];
	}

	int max = 0;
	if (max < cache[n].first) max = cache[n].first;
	if (max < cache[n].second) max = cache[n].second;
	if (max < cache[n - 2].second + scores[n]) max = cache[n - 2].second + scores[n];
	std::cout << max;
}

dldyddlwl 1년 전 0

	for (int i = 3; i <= n; ++i) {
		cache[i].first = cache[i - 1].second + scores[i];
		cache[i].second = std::max(cache[i - 2].first,cache[i-2].second) + scores[i];
	}

// i 로 가는 방법은, 
// 바로 2칸 뛰어넘는것 i-2 => i
// 그리고 i-3 에서 i-1로 뛰어넘은 후, i로 오는 것입니다. i-3 => i-1 => i (i-2와의 관계 생각!)

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

문제

문제

출처

ICPC

반례를 찾을 수 없습니다.. ㅠㅠ

mintflavoredwater 1년 전 0

dldyddlwl 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말