[Algorithm]Baekjoon 11060번 : 점프 점프

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

11060번: 점프 점프

 

 
 
int n;
int arr[1001];
int dp[1111] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    if (n == 1)
    {
        cout << 0;
        return 0;
    }
 
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    int answer = 0x3f3f3f3f;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 1; j <= arr[i]; ++j)
        {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
 
            if (i + j >= n - 1)
            {
                answer = min(answer, dp[i + j]);
            }
        }
    }
 
    if (answer == 0x3f3f3f3f) cout << -1;
    else cout << answer;
}
 

 

최근에 풀었던 dp문제와 업데이트방식이 유사해서 쉽게 접근할 수 있었다.

주어진 값을 이용해 뒤엣 부분을 업데이트하는 방식이다.

dp[i]는 i에 도달할 수 있는 최소의 경우의수값이 들어있다.

arr[i]에는 최대이동할 수 있는 칸수가 적혀있으니, 최대칸수가 3이라면 dp[i+1],dp[i+2],dp[i+3]에 dp[i]+1값을 업데이트하면 된다. 물론, dp[i]에는 최소값이긴 하지만, dp[i+1]이나 dp[i+2],dp[i+3]에는 이전에 이미 더 적은횟수로 도달한 경우의수가 있기 때문에 min으로 최소값업데이트하면 된다.

 

그리고 n값이 1일 경우, 무조건 0을 출력해야한다는걸 잊지말자.