[코드트리 챌린지] 4주차 DP l - 조건에 맞게 선택적으로 전진하는 DP / 최대 점프 횟수

 

https://www.codetree.ai/missions/2/problems/maximum-number-of-jumps/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[1005];
int dp[1005];
// i의 위치에 도달 했을 때 그 이전에 점프한 횟수가 최대가 되어야함
// i의 위치에 도달 시 이전 점프 횟수가 동일하다면 그건 같은 것

void Initialize() {
    dp[0] = 0;

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

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    Initialize();


    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // 이전 위치 + 점프 가능 거리 >= 현 위치
            // 경우만 dp[i]를 갱신 가능함
            // dp[i] = 이전에 점프해 온 거리 중 가능한 최대값 + 1
            if (j + arr[j] >= i) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxCnt = 0;
    for (int i = 0; i < n; i++) {
        maxCnt = max(maxCnt, dp[i]);
    }

    cout << maxCnt;
}

n을 입력받아 0~n까지 arr 배열을 초기화합니다.

Initialize()함수를 통해 dp를 진행하기 위한 기본 값을 초기화합니다.
dp[0]의 경우 시작 위치이며 이전에 점프를 한 적이 없으므로 0으로 초기화합니다.

i = 1 부터 시작하여 i보다 작은 값인 j를 통해 이전에 점프를 하여 i에 도달할 수 있는지를 확인합니다.
(이전 위치 + 이전 위치의 점프 가능 거리) >= (현 위치) 일 경우 점프를 통해 i에 도달할 수 있으므로
이때 dp[i] = dp[j]+1로 초기화 해주도록 합니다.

dp[i] = max(dp[j]+1) (0 <= j < n , j + arr[j] >= i) 이다.

이때 고민해봐야할 문제는 만약 dp[i]의 값이 시작 위치에서 점프하여 도달함으로써 초기화된 값이 아닌
다른 위치에서 시작하여 dp[i]에 도달할 경우 그 값이 최대가 되는 경우이다.
왜냐하면 이 문제의 경우 시작 위치에서 점프하여 가능한 최대 점프 횟수를 구하여야 하기 때문이다.

사실 이 문제는 Initialze() 함수 부분에서 해결되었는데 dp[0] 이외에 모든 곳을 INT_MIN으로 초기화
해줌으로써 아무리 증가한다고 하더라도 dp[0]에서 시작하여 도달할 수 있는 부분 이외에는 매우 작은 값
이 나오기 때문이다.

ex)
9
1 1 0 3 1 1 1 1 1
를 입력으로 받을 경우 dp 배열은 
0 1 2 -2147483648 -2147483647 -2147483646 -2147483645 -2147483644 -2147483643
이다.