11060번: 점프 점프

문제접근🤔

• 입력을 받을때마다 그 숫자가 갈 수 있는 공간에 모두 방문을 하면서 더 작은 값을 비교

놓쳤던 부분😅

• dp의 자료형 Int 범위 초과인줄 알고 dp에 long long을 줘서 맞췄었는데 그게 아니었음
• dp를 int범위 최대값을 넣어버려서 dp[i] + 1이 동작하는 경우 버퍼오버플로우 발생. 그래서 long long으로 하면 정답이 되는거였음

코드😁

2020 KB

0 ms

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

#define MAX 214748364

int main(void) {
	int n;
	int input;
	int dp[1001];

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	fill(dp, dp + 1001, MAX);

	cin >> n;
	dp[1] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> input;
		for (int j = 1; j <= input; j++) {
			if (i + j > 1000)
				break ;
			dp[i + j] = min(dp[i + j], dp[i] + 1);
		}
	}
	if (dp[n] == MAX)
		cout << "-1";
	else
		cout << dp[n];
	return (0);
}