BOJ 4655 - Hangover

문제

BOJ 4655 - Hangover

카드를 테이블 끝에서부터 n번째 카드까지 쌓을 때, k번째 카드는 아래 카드 묶음 위로 1/(k+1)만큼 돌출된다. 주어진 돌출 길이 c 이상이 되기 위해 필요한 카드 수를 구한다. 즉, 조화급수의 부분합 1/2 + 1/3 + ... + 1/n >= c를 만족하는 최소 n-1을 찾는 문제다.

입력

• 여러 줄에 걸쳐 실수 c가 주어진다 (0.01 이상 5.20 이하).
• 0.00이 입력되면 종료한다.

출력

• 각 c에 대해 필요한 카드 수와 card(s)를 출력한다.

예제

풀이

조화급수의 부분합을 순서대로 누적하면서 목표값 이상이 되는 시점을 찾는 시뮬레이션이다.

1. 실수 N을 입력받는다. N이 0이면 종료한다.
2. i를 2부터 시작하여 sum += 1/i를 반복 계산한다.
3. sum이 N 이상이 되면 i - 1을 출력한다 (카드 수는 i-1장).

핵심 아이디어: n장의 카드를 쌓을 때 돌출량은 1/2 + 1/3 + ... + 1/(n+1)이다. 이 조화급수 부분합이 c 이상이 되는 최소 항 수를 구한다.

코드

#include <iostream>
#define ll long long
using namespace std;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  double N;
 
  while (true)
  {
    cin >> N;
    if (N == 0)
      break;
 
    double i = 2, sum = 0;
    for (;; i += 1)
    {
      sum += 1 / i;
      if (sum >= N)
      {
        cout << i - 1 << " card(s)\n";
        break;
      }
    }
  }
}

복잡도

• 시간: O(H) — H는 목표값 c를 충족하기 위한 조화급수 항 수 (c=5.20일 때 약 83항)
• 공간: O(1)