글 읽기 - dp로 풀었는데 반례를 잘모르겠습니다...

drone1575 2년 전 0

dp[i] => i번째 칸으로 가기 위한 최소의 점프 횟수. 이렇게 정해서 풀어봤습니다.

dp배열의 요소를 INF로 초기화시켜서 맨 오른쪽 칸이 INF일 경우 -1이 출력 되도록 해봤습니다.

어디서 틀렸는지 잘 모르겠습니다. 도와주실 수 있을까요?..

#include <iostream>
using namespace std;
#define N 1001
#define INF 105

int main()
{
	int dp[N], arr[N] = { 0 };
	int n;
	
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		dp[i] = INF;
	}
	
	dp[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (j <= arr[i - j])
			{
				dp[i] = min(dp[i], dp[i - j] + 1);
			}
		}
	}

	if (dp[n] == INF)
	{
		cout << "-1\n";
	}
	else
	{
		cout << dp[n] << "\n";
	}

	return 0;
}

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

문제

문제

출처

ICPC

dp로 풀었는데 반례를 잘모르겠습니다...

drone1575 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말