C++를 사용하여 계단 수 찾기

이 문제에서 우리는 계단을 만들기 위해 제공된 벽돌의 수를 나타내는 숫자 N이 주어집니다. 우리의 임무는 f 계단 수 .

주어진 벽돌을 사용하여 계단을 만들어야 합니다. 각 단계는 마지막 단계보다 벽돌이 하나 더 필요합니다. 그리고 첫 번째 단계는 두 개의 벽돌 높이입니다. 우리는 벽돌로 만들 수 있는 그러한 단계의 수를 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

N = 40

출력

3

설명

단계 =1; 필요한 벽돌 =2; 사용된 총 벽돌 =2; 남은 벽돌 =38

단계 =2; 필요한 벽돌 =3; 사용된 총 벽돌 =5; 남은 벽돌 =35

단계 =3; 필요한 벽돌 =4; 사용된 총 벽돌 =9; 남은 벽돌 =31

단계 =4; 필요한 벽돌 =5; 사용된 총 벽돌 =14; 남은 벽돌 =26

단계 =5; 필요한 벽돌 =6; 사용된 총 벽돌 =20; 남은 벽돌 =20

단계 =6; 필요한 벽돌 =7; 사용된 총 벽돌 =27; 남은 벽돌 =13

단계 =7; 필요한 벽돌 =8; 사용된 총 벽돌 =35; 남은 벽돌 =5

8단계에는 9개의 브릭이 필요하고 5개만 있으므로 추가 단계는 생성할 수 없습니다.

솔루션 접근 방식

문제에 대한 간단한 해결책은 루프를 사용하는 것입니다. 2에서 시작하여 사용된 브릭의 수가 N을 초과할 때까지 반복한 다음 마지막 단계의 수를 반환합니다.

이 솔루션은 좋지만 시간 복잡도는 N차수입니다. 그리고 합 공식과 이진 검색을 사용하여 솔루션을 찾는 더 나은 접근 방식을 만들 수 있습니다.

필요한 모든 벽돌의 합이 있으므로 항상 (n*(n+1)) /2보다 생성되는 사용되는 총 벽돌 수인 X가 있습니다. 이 경우 mid와 mid - 1에서 찾은 두 값 중 하나의 솔루션이 있습니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int findStairCount(int T){
   int low = 1;
   int high = T/2;
   while (low <= high) {
      int mid = (low + high) / 2;
      if ((mid * (mid + 1)) == T)
         return mid;
      if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
         return mid - 1;
      if ((mid * (mid + 1)) > T)
         high = mid - 1;
      else
         low = mid + 1;
      }
   return -1;
}
int main(){
   int N = 60;
   int stepCount = findStairCount(2*N);
   if (stepCount != -1)
      stepCount--;
   cout<<"The number of stair steps that can be made is "<<stepCount;
   return 0;
}

출력

The number of stair steps that can be made is 9