백준 11060번 점프 점프

문제 링크 : https://www.acmicpc.net/problem/11060

11060번: 점프 점프

문제 요약

 

1. 재환이는 일직선에 미로의 첫 번째 칸에 적혀있다. 그리고 N번째 칸으로 도착하는 것이 목표다.

2. 일직선 미로의 각 칸에는 숫자가 입력되어있다. 재환이는 N번째 칸에 있을 경우, N번째 칸에 있는 숫자만큼 최대 점프가 가능하다.

3. 예를들어 첫 번째 칸에 2가 적혀있을 경우, 재환이는 1칸을 점프하거나 2칸을 점프할 수 있다.

4. N번째 칸에 도달하기 위한 최소 점프 횟수를 출력하라. 불가능 할 경우 -1을 출력하라.

 

핵심 포인트

 

이 문제는 Leetcode 45. Jump Game II와 거의 동일한 문제입니다.

LeetCode 45. Jump Game II

2중 for문을 돌렸다가는 시간초과가 날 수 있으므로, Dynamic Programming을 활용하는 것이 핵심입니다.

다만 부분 부분 놓칠수 있는 포인트가 있으므로, 그러한 부분들을 잘 파악하는 것이 핵심입니다.

 

문제 풀이

 

1. 필요한 변수를 선언하고 값을 저장합니다. 아래 코드에서 (3)번째 항목은 간과하기 쉬운 포인트입니다.

    int n = 0, temp;
    cin >> n;
    vector<int> v(n); // 1
    vector<int> ans(n,0); // 2
    if (n == 1) { // 3
        cout << 0 << "\n";
        exit(0);
    }
    for (int i = 0; i < n; i++) cin >> v[i];

(1) 미로의 정보를 저장할 벡터입니다.

(2) 누적 점프 횟수를 기록할 벡터입니다. 선언과 동시에 모두 0으로 초기화해줍니다.

(3) 만약 n==1일 경우, 재환이는 시작과 동시에 n번째 칸에 도달했음을 뜻합니다. 바로 0을 출력하고 종료하면 됩니다.

 

2. 다음은 누적 점프 횟수를 기록하는 for문 입니다.

여기서 (3)번 ~ (5)번의 간과할 수 있는 포인트를 유의깊게 보시면 됩니다.

for (int i = 0; i < n; i++) { // 1
        for (int j = i + 1; j <= i + v[i]; j++) { // 2
            if (j >= n) break; // 3
            if (ans[j] != 0) continue; // 4
            if (i != 0 && ans[i] == 0) break; // 5
            ans[j] = ans[i] + 1; // 6
            if (j == n - 1 && ans[j] != 0) { // 7
                cout << ans[j] << "\n";
                exit(0);
            }
        }
    }
    cout << -1 << "\n"; // 8

(1) 0부터 n-1까지, 미로의 모든 구역을 방문합니다.

(2) 이 for문은 점프를 했을때 이동 가능한 구역을 뜻합니다. i+1부터 i+v[i] 이하까지 방문합니다.

(3) 만약 j가 n 이상일 경우, 범위를 초과했으므로 break를 합니다.

(4) 만약 ans[j]가 0이 아닐 경우, 이미 방문해서 최소 점프 횟수를 갱신했음을 뜻합니다. 이 경우엔 continue를 해줍니다.

(5) 만약 i가 0이 아닌데 ans[i]가 0인 경우, 갈 수 없는 지역을 뜻합니다. 이 부분이 이해 안될 경우 아래 도표의 v[2]를 주의깊게 봐보시면 됩니다.

v[0]	v[1]	v[2]	v[3]	v[4]
1	1	0	1	1

(6) ans[j] 는 ans[i] + 1로 갱신합니다. 이는 시작 지점에서 점프를 한 번 해서 해당 지점에 도달했음을 뜻합니다.

(7) 현재 좌표가 n-1이고, 동시에 해당 좌표의 누적 점프 횟수가 0이 아니라면 정답을 출력하고 종료하면 됩니다.

(8) 모든 for문을 빠져나왔을 경우 정답이 존재하지 않는다는 뜻이므로 -1을 출력합니다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, temp;
    cin >> n;
    vector<int> v(n);
    vector<int> ans(n,0);
    if (n == 1) {
        cout << 0 << "\n";
        exit(0);
    }
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= i + v[i]; j++) {
            if (j >= n) break;
            if (ans[j] != 0) continue;
            if (i != 0 && ans[i] == 0) break;
            ans[j] = ans[i] + 1;
            if (j == n - 1 && ans[j] != 0) {
                cout << ans[j] << "\n";
                exit(0);
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}