백준 27961번 고양이는 많을수록 좋다 - C++

문제

---

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N$N$마리를 집에서 키우기로 결심했다!

마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

• 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
• 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 k$k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.

마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 N$N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

 

입력

첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.

 

출력

첫 번째 줄에 정확히 $N$마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.

 

문제 링크

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

 

 

풀이

---

전형적인 그리디 문제다.

이 문제는 문제에 나와있는대로 1에서부터 시작해서 고양이 수를 정확히 맞추려고 하면 안되는 문제다.

문제의 조건에는 복제 마법은 $k$마리가 존재할 때, $0$부터 $k$마리를 생성할 수 있는 마법이라고 나와있으니, 절반만 넘기면 나머지는 알아서 채울 수 있다.

 

그러면 절반까지 얼마나 최적으로 갈 수 있냐가 핵심인데, 복제마법을 사용할 때 $k$마리를 생성하면 된다.

즉, 계속 2배를 해주면 된다는 것이다.

아주 당연하게도 생성 마법은 처음에만 사용하고 그 뒤로는 사용할 일이 전혀 없다.

 

 

C++ 코드

---

#include <iostream>

using namespace std;

long long N, answer = 1;

void input() {
  cin >> N;
}

void solve() {
  long long cat = 1;

  while (true) {
    if (cat >= N) {
      break;
    }
    cat = cat * 2;
    ++answer;
  }
}

void output() {
  if (N == 0) {
    cout << 0 << endl;
  } else {
    cout << answer << endl;
  }
}

int main() {
  input();
  solve();
  output();
}

 

변수의 범위에 조심하자...

그리고 $N$이 0이 될 수 있다는 것에도 조심해야한다.