[백준 / BOJ] C++ 27961 고양이는 많을수록 좋다

27961번: 고양이는 많을수록 좋다

 

문제

https://www.acmicpc.net/problem/27961

27961번: 고양이는 많을수록 좋다

 

 

풀이

처음에 고양이는 0마리 있고, 1마리 생성하거나 현재 K마리의 고양이가 있으면 1~K마리의 고양이를 복제하는 것이 가능하다. 즉, 고양이가 1마리 이상 있을 때는 복제 연산만 사용하면 된다. 이때, 정확히 N마리의 고양이를 만들어야 하므로 2 * K ≥ N 이 되는 순간 연산이 종료된다. 따라서 2의 제곱승 꼴로 증가시키다가 N 이상이 되는 순간까지의 횟수다.

 

이렇게 구현을 해도 되지만 (log2 N) + 1을 출력해도 될 것 같다. (+1을 하는 이유는 맨 처음 1마리를 생성하는 연산 때문)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, ans = 0, a = 0;
  cin >> n;
  while (a < n) {
    if (a == 0)
      a++;
    else 
      a *= 2;
    ans++;
  }
  cout << ans;
  return 0;
}