글 읽기 - 왜 틀렸는지 모르겠습니다... 반례가 있을까요?

banana970 2년 전 0

뒤에서 부터 맨 앞까지 DP를 이용해 탐색하였습니다.

질문 게시글에 있는 모든 반례가 정답으로 나오는데, 어디가 틀렸는지 모르겠습니다.

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

using namespace std;
int N;
int list[1001] = {};
int save[1001] = {};
int Min = 100;

void DP(int index) {
	save[N] = 0;
	int Min = 100;
	
	for (int i = N - 1; i >= 0; i--) {
		
		if (list[i] == 0) {
			save[i] = -1;
			continue;
		}
		Min = 100;
		for (int j = 1; j <= list[i]; j++) {
			if (i + j > N ) { 
				break;
			}
			if (save[i + j] < Min && save[i + j] != -1) {
				Min = save[i + j];
			}
		}
		if (Min == 100) { save[i] = -1; }
		else { save[i] = Min + 1; }
	}
	return;
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> list[i];
	}
	N -= 1; // index를 기준으로 하기 위해
	if (N == 0) {
		cout << 0;
		return 0;
	}
	DP(0);
	cout << save[0];
}

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다... 반례가 있을까요?

banana970 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말