18265 - MooBuzz

문제

** 오역 주의

농부 존의 소들은 최근에 "FizzBuzz" 라 불리는 간단한 숫자 게임의 팬이 되었습니다. (...?)
게임의 규칙은 간답합니다.
원모양으로 서 있는 상태에서 소들은 1부터 차례대로 숫자를 세고,
각각의 소는 자신의 차례가 되면 하나의 숫자를 말합니다.
만약 한 소가 3의 배수에 해당하는 숫자를 말할 차례가 되면, 숫자 대신 "Fizz" 를 말해야 합니다.
만약 한 소가 5의 배수에 해당하는 숫자를 말할 차례가 되면, 숫자 대신 "Buzz" 를 말해야 합니다.
만약 한 소가 15의 배수에 해당하는 숫자를 말할 차례가 되면, 숫자 대신 "FizzBuzz" 를 말해야 합니다.
게임의 첫 부분은 아래와 같이 진행됩니다.

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

소들은 제한된 어휘력을 가져서 FizzBuzz 게임을 할 때, Fizz,Buzz,FizzBuzz 를 말하는 대신 "Moo" 를 말합니다.
소들이 하는 게임의 버전은 다음과 같이 진행됩니다.

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

숫자 N(1~10⁹) 이 주어졌을 때, 이 게임에서 N 번째로 말한 번호를 구하세요

입력과 출력

• 입력 : 숫자 N
• 출력 : N 번째로 말하는 숫자

ex)
input :4 ouput: 7


숫자 3 , 5, 6은 "Moo" 로 말하기 때문에 4번째로 말하는 숫자는 7이다.
1 -> 2 -> 4 -> 7

풀이

특정 숫자 x 에서 3,5, 15 를 뺀 숫자의 개수는
x - (x/3 + x/5 - x/15)

위의 값이 N 과 동일한 x 를 찾아야 한다.

일일이 모든 숫자를 비교해가면 되겠지만 시간 초과가 날 듯 하다.

일단 생각난 방법으로는 x ~ 2x 범위 내에서 이분 탐색을 하며 찾는것이다.
그럴려먼 2x 내에 있는 3,5,15 를 제외한 숫자의 개수가 항상 x 보다 커야 한다.
이게 보장이 되는지 계산을 해보자

2x - (2x/3 + 2x/5 - 2x/15) > x
즉, x > (2x/3 + 2x/5 - 2x/15) 가 보장이 되면 된다.

2x/3 은 실상 다 반내림 되니까 양쪽 식에 15를 곱했다고 생각하자.

15x > 10x + 6x - 2x = 14x

보장이 된다!!

x ~ 2x 사이를 이분 탐색하면서 찾기만 하면 된다. O(logn) 이다!

주의 사항

이분 탐색시 찾은 숫자가 3이나 5의 배수이면, 해당 숫자 이전의 숫자를 출력 해줘야 한다.
예를 들어 13번째 숫자를 찾는데, 실제 정답은 23이지만 24또한 3,5,15 배수를 제외한 숫자가 13개여서
조건을 만족해 버린다.

그래서 찾은 숫자가 3,5 의 배수일 경우에는 해당 숫자 -1 or -2 를 한 숫자를 출력해줘야 한다.

코드

#include <iostream>

using namespace std;
using numtype = unsigned long long int;

int main() {
  int n;

  cin >> n;
  numtype start = n;
  numtype end = 2*n;

  while(start <= end) {
    numtype middle = start/2 + end/2; //
    numtype result = middle - (middle/3 + middle/5 - middle/15);

    if(result == n) {
      if(middle % 3 == 0 || middle % 5 == 0 ) {
          if((middle-1) %3 == 0 || (middle-1) % 5 ==0) {
              cout << middle-2 << "\n";
          }
          else
            cout << middle -1 << "\n";
      } else {
        cout << middle << "\n";
      }
      return 0;
    }

    if(result < n)
      start = middle;
    else
      end = middle;

  }
}