C++로 구현하는 개구리 최소 점프 문제 풀이

길이가 n인 이진 문자열 S와 정수 d가 하나씩 주어져 있다고 가정해 보겠습니다. 수직선 위에서 개구리는 1번 지점에서 출발해 n번 지점까지 이동해야 합니다. 개구리는 한 번의 점프로 오른쪽 방향으로 최대 d만큼 움직일 수 있으며, 1부터 n까지 각 지점에는 연꽃이 있으면 1, 없으면 0이 표시되어 있습니다. 개구리는 연꽃이 있는 지점에만 착지할 수 있습니다. 따라서 우리가 구해야 하는 것은 개구리가 n에 도달하기 위해 필요한 최소 점프 횟수이며, 도달이 불가능한 경우에는 -1을 반환해야 합니다.

예를 들어 입력이 S = "10010101", d = 4라면 출력은 2가 됩니다. 개구리가 1번 위치에서 4번 위치로 점프한 뒤, 이어서 인덱스 8(n)로 점프하기 때문입니다.

풀이 접근 방법

이 문제는 그리디(greedy) 기법으로 해결할 수 있습니다. 핵심 아이디어는 현재 위치에서 가능한 한 멀리, 즉 d만큼 점프하는 것입니다. 착지하려는 지점에 연꽃이 없다면 한 칸씩 뒤로 물러나면서 연꽃이 있는 지점을 찾습니다. 점프 횟수가 n을 초과하면 더 이상 앞으로 나아갈 수 없다고 판단하고 -1을 반환합니다.

알고리즘 단계

n := 문자열 s의 길이
x := 0
y := 0
x < n - 1 이고 y <= n인 동안 반복:
    만약 s[x]가 '1'이면:
        x := x + d
        y를 1 증가
    그렇지 않으면:
        x를 1 감소
만약 y >= n이면:
    return -1
그렇지 않으면:
    return y

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d){
    int n = s.size();
    int x = 0, y = 0;
    while (x < n - 1 && y <= n){
        if (s[x] == '1')
            x += d, ++y;
        else
            --x;
    }
    if (y >= n)
        return -1;
    else
        return y;
}
int main(){
    string S = "10010101";
    int d = 4;
    cout << solve(S, d) << endl;
}

입력

"10010101", 4

출력

2

이처럼 매 순간 최대한 멀리 점프하려 시도하고, 조건에 맞지 않으면 뒤로 한 칸씩 조정하는 방식을 사용하면 개구리가 목표 지점까지 도달하는 데 필요한 최소 점프 횟수를 효율적으로 구할 수 있습니다.