[BOJ] 11060번 점프점프

생각 정리

1. dp[i]를 점프해야 하는 최소 횟수로 정의

2. 횟수가 제일 많은 경우는 n이 1000이고, 입력된 숫자가 모두 1일 때라고 생각(-1이 나오지 않는 범위에서) -> 시간 초과가 나지 않는다고 생각.

3. 점프해야 하는 최소 횟수를 정의하라고 했기 때문에 dp의 모든 인덱스를 아주 큰 수로 초기화

4. a[i]에 입력된 수만큼 떨어진 곳 이하에 점프해야 하는 최소 횟수를 대입하고, 미리 저장되어 있는 최소 횟수와 그 이후 들어온 횟수를 비교해서 min 값을 저장

5. dp[n]이 987654321로 남아있다면 도달하지 못한 것이므로 -1을 출력

---

소스코드

#include <iostream>
#include <string.h>
#include <algorithm>

#define MAXNUM 987654321
using namespace std;

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

	int n,dp[1002], a[1002];
	
	cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = MAXNUM;
	}

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	dp[1] = 0;
	for (int i = 1; i <= n; i++) {
		int cur = a[i];
		for (int j = i+1; j <= cur+i; j++) {
			if (j > n) continue;
			dp[j] = min(dp[i]+1, dp[j]);
		}
		
	}

	if (dp[n] == MAXNUM) cout << -1;
	else cout << dp[n];

}