[Silver V] Jumping Frog - 26316

[문제 위치]

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

[문제 풀이]

이 문제는 1차원으로 나열된 길이 c의 칸에서, 시작(첫 칸)부터 도착(마지막 칸)까지 “최소 점프 횟수”를 구하는 문제이다. 어떤 날에는 한 번 점프할 때 최대 d개의 칸을 “넘어” 뛸 수 있으므로, 실제로는 앞으로 최대 (d+1)칸까지 이동할 수 있다. ‘X’인 칸은 착지할 수 없지만, 그 위를 “넘어가는” 것은 허용된다. 또한 점프는 항상 도착 방향(오른쪽)으로만 한다.

이를 해결하기 위해 동적 계획법을 사용한다. i번째 칸(0-index)에 도달하는 최소 점프 횟수를 dp[i]라고 두고, 도달 불가능하면 매우 큰 값(INF)으로 둔다. 시작점은 dp[0]=0이다. i번째 칸이 ‘X’이면 착지 불가이므로 dp[i]=INF로 둔다. i번째 칸이 ‘.’이면, 직전 착지 위치 j는 i-(d+1) ≤ j ≤ i-1 범위 중 하나여야 하므로 다음 점화식을 쓴다.

dp[i] = min(dp[j] + 1) (j ∈ [max(0, i-(d+1)), i-1])

최종 정답은 dp[c-1]이며, INF라면 도달 불가능이므로 0을 출력한다. 출력은 각 데이터셋마다 “Day #k”, 그 다음 입력의 c d와 문자열을 그대로 출력하고, 마지막에 답을 출력한 뒤 빈 줄을 한 줄 추가한다.
아래는 이를 구현 코드이다.

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

using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO

    int n;
    cin >> n;

    for (int day = 1; day <= n; day++) {
        int c, d;
        string s;
        cin >> c >> d >> s;

        const int INF = 1e9;
        vector<int> dp(c, INF);
        dp[0] = 0;

        int maxStep = d + 1; // 한 번에 1~(d+1)칸 이동 가능

        for (int i = 1; i < c; i++) {
            if (s[i] == 'X') continue; // 착지 불가
            int start = max(0, i - maxStep);
            for (int j = start; j <= i - 1; j++) {
                if (dp[j] == INF) continue;
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }

        int ans = (dp[c - 1] == INF ? 0 : dp[c - 1]);

        cout << "Day #" << day << "\n";
        cout << c << " " << d << "\n";
        cout << s << "\n";
        cout << ans << "\n\n";
    }

    return 0;
}