[C++] 99클럽 코테 스터디 16일차 TIL - 고양이는 많을수록 좋다

🍟
문제 사이트: 백준
문제 난이도: Bronze I
문제 번호: 27961

 

🚩 문제

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

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

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

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

🚩 입력

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

🚩 출력

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

⚙️ 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long N;
    cin >> N;

    if (N <= 1) {
        cout << N << '\n';
    } else {
        int moves = 1;  // 최소 생성 마법

        // 복제 마법
        while (N > 1) {
            N = ceil(N / 2.0);  // 올림 처리
            moves++;
        }

        cout << moves << '\n';
    }

    return 0;
}

메모리: 2020 KB, 시간: 0 ms

 

 

 

🤔 코드 풀이

가장 좋은 선택을 반복해서 문제를 푸는 그리디 알고리즘이다.

먼저 N이 크므로 long long으로 선언해 준다.

0마리, 1마리의 경우에는 생성마법만 필요하다. 따라서 그대로 N을 출력한다.

이외에는 복제마법이다.

최소 한 번의 생성마법으로 1을 만들어야 하므로 초기값을 1로 설정한다.

이후 고양이 수를 반으로 줄이면서 복제 마법을 사용한다. 이때 고양이 수가 홀수면 1마리가 부족해지기 때문에 반올림 처리가 필요하다.

 

⏱️ 코드 시간 복잡도

전체 시간복잡도는 O(logN)이다.