백준11060 - 점프 점프

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

경우의 수가 생각보다 많은 문제였다. 1차원 dp를 사용하여 풀었다. 

 

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

int n;
int mat[1001];
int d[1001];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> mat[i];
	}

	for (int i = 1; i <= n; i++) {
		if (i == 1) { //출발 지점인 경우
			if (mat[i] == 0) { //처음 시작하는 지점이 0이면
				break; //아무대도 못감
			}
			else { //처음 시작하는 지점이 0이 아닌 어떤 수이면
				/* 
					두 가지 조건을 만족해야 함
					1. 2번지 부터 시작해서 처음 출발지가 최대한 갈 수 있는 거리
					2. 최대한 갈 수 있는 거리가 주어진 거리보다 작은 지점이여야 한다.
				*/
				for (int j = 2; j <= 1 + mat[i] && j <= n; j++) { 
					d[j] = 1;
				}
			}
		}
		else { //출발 지점이 아닌 경우
			if (d[i] != 0 && mat[i] != 0) { //현재 위치까지 이동할 방법이 있고 현재 위치에서 갈 수 있는 거리가 0이 아닌 경우
				for (int j = i; j <= i + mat[i] && j <= n; j++) {
					if (d[j] == 0) { //이동하려는 위치가 0이면
						d[j] = d[i] + 1; //i로 갈 수 있는 방법에서 +1을 한다.
					}
					else { //이동하려는 위치가 이미 갈 수 있는 수가 있다면
						d[j] = min(d[j], d[i] + 1); //이미 있는 값과 이동한 결과의 값을 비교하여 작은 값을 넣는다.
					}
				}
			}
		}
	}

	if (n == 1) { //한 가지 밖에 위치가 주어진 경우
		cout << 0; //0출력
	}
	else if (mat[1] == 0 || d[n] == 0) { //처음 출발하는 지점이 갈 수 있는 거리가 없거나 n번지에 갈 수 없는 경우
		cout << -1; //-1출력
	}
	else { //그 외의 경우
		cout << d[n]; //n번지에 갈 수 있는 최소 방법 출력
	}
}