[백준/BOJ] 11060번 점프점프 (C++)

www.acmicpc.net/problem/11060

11060번: 점프 점프

DP 유형의 문제입니다.

 dp 배열을 임의의 큰 값 2147000000으로 초기화해주고, 0번째 인덱스는 0으로 초기화합니다. 그런 다음 0번에서 n-1번 인덱스 각각 최대 1번부터 a[i]번 까지 움직여보면 되는 문제입니다.

 

#include <iostream>
using namespace std;

int a[1001], dp[1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 0;
    cin >> n;
    for(int i = 0; i < n; i++) {
    	cin >> a[i];
    	dp[i] = 2147000000;
	}
	
	dp[0] = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 1; j <= a[i]; j++) {
			if(dp[i] != 2147000000) dp[i + j] = min(dp[i + j], dp[i] + 1);
		}
	}
	
	if(dp[n - 1] == 2147000000) cout << "-1";
	else cout << dp[n - 1];
}