[2976] NIKOLA

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

2976 - NIKOLA

본문

Nikola는 자신의 의지와는 상관없이 어떤 게임 속의 메인 캐릭터가 되어버렸다! 이 게임은 $1$부터 $N$까지의 번호가 쓰인 일렬로 된 $N$개의 발판 위에서 진행된다. Nikola는 $1$번 발판 위에서 시작하여 다른 발판 위로 점프하여 이동할 수 있다. 처음 이동할 때는 무조건 $2$번 발판 위로 움직이게 되어 있으며, 이후의 이동에는 다음과 같은 제약이 따른다.

• 양의 방향으로 이동할 경우 바로 전 단계보다 1칸 더 먼 거리로 점프해야 한다.
• 음의 방향으로 이동할 경우 바로 전 단계에서 이동한 거리 만큼 점프할 수 있다.

예를 들어, 첫 번째 점프 이후($2$번째 발판 위에 있는 상황), Nikola는 $4$번 발판으로 뛰어 갈 수 있으며, 반대 방향인 $1$번 발판으로 뛰어 갈 수 있다.

그가 매번 각 발판 위에 도달 했을 때, 해당 구역의 통행료를 내야만 한다. Nikola는 가능하다면 $N$번 발판까지 이동하면서 지불해야 하는 통행료를 최소로 만들고 싶어한다.

입력

첫째 줄에는 발판의 개수 $N$이 $2 \leq N \leq 1\,000$ 인 정수로 주어진다.

둘째 줄부터 $N+1$번째 줄에는 $1$번 발판부터 $N$번 발판까지 순서대로 각 발판 위로 점프하는데 지불해야 하는 통행료가 주어지며, 이들은 모두 $500$ 이하의 양의 정수이다.

출력

Nikola가 $N$번째 발판에 도달하기 위한 통행료의 최솟값을 첫 번째 줄에 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

풀이 방법을 바로 떠올리는 것이 쉽지는 않았다. 칸의 개수가 1천개밖에 되지 않으므로, bfs로 시뮬레이션 돌리듯 모든 경우를 탐색했었다. 그리고 그때마다 가능한 최솟값을 기록하고, 같은 상황에 도달했을 때 이미 기록된 값이 더 작을 경우 탐색을 멈추는 가지치기 방법까지 구현했다. 결과는 시간초과. 그래서 완전탐색으로는 구현이 불가능하다고 생각했다.

완전탐색 구현을 진행하면서 case가 겹치는 상황이 생긴다는 것을 확인했다. “특정 위치 $x$에 현재 step $s$만큼 움직였을 때” 라는 상황에 지금까지의 cost의 최솟값을 기록한다고 치면, 이 문제가 dp문제로 바뀌어보이는 기적이 일어난다.

step은 1씩 증가하거나 그대로인 경우만 존재하므로, step을 증가시키는 방향으로 dp값을 모두 구해놓는 방법을 사용할 수 있다. 특정 칸에서부터 사용할 수 있는 action은 2개로, step을 1 늘리면서 앞으로 가는 것과 step 크기만큼 뒤로 가는 것이 있다. dp값을 활용하기 위해서, dp값을 구하는 순서도 약간 조절하여 계산하도록 하자.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 10 / 10

#include <stdio.h>

#define MAX_IDX (1000 + 1)
const int start = 1;
const int INF = 987654321;

int cost[MAX_IDX];
int dp[MAX_IDX][MAX_IDX];
int end;
int result = INF;

#define min(a, b) (((a) > (b)) ? (b) : (a))

void init(int x) {
    for (int i = 0; i <= x; ++i) {
        for (int j = 0; j <= x; ++j) {
            dp[i][j] = INF;
        }
    }

    dp[start][0] = 0;
    return;
}

int main() {
    scanf("%d", &end);
    for (int i = 1; i <= end; ++i) {
        scanf("%d", cost + i);
    }
    init(end);

    for (int c = 1; c <= end; ++c) {  // jump width
        for (int x = c; x <= end; ++x) {
            dp[x][c] = min(dp[x][c], dp[x - c][c - 1] + cost[x]);
        }

        for (int x = end - c; x > 0; --x) {
            dp[x][c] = min(dp[x][c], dp[x + c][c] + cost[x]);
        }
    }

    for (int i = start; i <= end; ++i) {
        result = min(result, dp[end][i]);
    }
    printf("%d", result);

    return 0;
}