개구리가 집에 도달하는 최소 점프를 찾는 C++ 코드

n 비트와 다른 숫자 d가 있는 하나의 이진 문자열 S가 있다고 가정합니다. 숫자 라인에서 개구리는 점 1에서 시작하여 점 n에 도달하려고 합니다. 개구리는 d보다 크지 않은 거리에서 오른쪽으로 점프할 수 있습니다. 백합 꽃이 있으면 1에서 n까지의 각 점에 대해 1로 표시하고 그렇지 않으면 0으로 표시합니다. 개구리는 백합이 있는 지점에서만 점프할 수 있습니다. 개구리가 n에 도달하는 데 필요한 최소 점프 수를 찾아야 합니다. 가능하지 않으면 -1을 반환합니다.

따라서 입력이 S ="10010101"과 같으면; d =4이면 위치 1에서 4로 점프한 다음 인덱스 8(n)로 점프하기 때문에 출력은 2가 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of s
x := 0
y := 0
while (x < n - 1 and y <= n), do:
   if s[x] is same as '1', then:
      x := x + d
      increase y by 1
   Otherwise
      (decrease x by 1)
if y >= n, then:
   return -1
Otherwise
   return y

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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