글 읽기 - 2156번 반례를 모르겠습니다 ㅠ

hhb9817 3년 전 0

게시판에 있는 거의 모든 반례를 돌려보았으나 문제가 없는데 왜 틀리는지 감이 오질 않습니다..

어떤 문제가 있는걸까요?

도움 주시면 정말 감사하겠습니다!!

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;
int map[10001] = {};
int one_step_ans[10001] = {};
int two_step_ans[10001] = {};

void find(int n){
	if(one_step_ans[n] != -1){
		return;
	}
	if(two_step_ans[n] != -1){
		return;
	}
	if(n == 1){
		one_step_ans[1] = map[1];
		two_step_ans[1] = 0;
		return;
	}
	if(n == 2){
		one_step_ans[2] = map[1] + map[2];
		two_step_ans[2] = map[2];
		return;
	}
	if(n == 3){
		one_step_ans[3] = map[2] + map[3];
		two_step_ans[3] = map[1] + map[3];
		return;
	}
	find(n-1);
	find(n-2);
	find(n-3);
	one_step_ans[n] = two_step_ans[n-1] + map[n];
	two_step_ans[n] = max(max(one_step_ans[n-2], two_step_ans[n-2]), max(one_step_ans[n-3], two_step_ans[n-3])) + map[n];
	return;
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);

	int n;
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> map[i];
		one_step_ans[i] = -1;
		two_step_ans[i] = -1;
	}
	
	find(n);
	
	cout << max(max(one_step_ans[n], two_step_ans[n]), max(one_step_ans[n-1], two_step_ans[n-1]));
	
    return 0;
}

sweetlulu486 3년 전 0

항상 현재 i번째는 마신다는 가정하에

i-1에 마신거 안 마신거 기준으로 풀어보세요

i i-1 i-2 i-3

O [O] X O

O [X] O

감이 오시나요?

바텀업 기준으로 첫째 잔과 둘째 잔은 항상 선택하는게 최선이므로 값을 정해주시면 될거 같아요.

sweetlulu486 3년 전 0

해당문제는 boj.kr/9465 와 같이 선택해도 피해를 볼 수 있는 경우의수가 아닌 이상 항상 현재 술에는 선택하는게 최선입니다.

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

문제

문제

출처

ICPC

2156번 반례를 모르겠습니다 ㅠ

hhb9817 3년 전 0

sweetlulu486 3년 전 0

sweetlulu486 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말