백준 27961 마도카 고양이

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

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

마법소녀 마도카는 N마리의 고양이를 최소한의 행동 횟수로 생성하려 한다.
초기에는 고양이가 없으며, 다음 두 가지 마법을 사용할 수 있다

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

마도카는 위의 2가지 마법을 적절히 사용하여, 마도카가 정확히 N마리의 고양이를 만들기 위해 필요한 최소 행동 횟수를 구하라. 🚀

 

#include<iostream>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long CatNum;
    cin >> CatNum;

    long long MinMagicNum = 0;
    long long CurrentCatNum = 1;

    // 아무 고양이도 원하지 않는 경우
    if (CatNum == 0) 
    {
        cout << 0 << '\n';
        return 0;
    }

    // 첫 번째 고양이 생성
    MinMagicNum = 1;

    // 목표 고양이 수에 도달할 때까지
    while (CurrentCatNum < CatNum) 
    {
        if (CurrentCatNum >= CatNum - CurrentCatNum) 
        {
            CurrentCatNum += (CatNum - CurrentCatNum);
            MinMagicNum++;
            break;
        }
        CurrentCatNum += CurrentCatNum;
        MinMagicNum++;
    }

    cout << MinMagicNum << '\n';
    return 0;
}

🔍  핵심은 "처음에 한 마리만 생성하고, 이후에는 복제만 사용"하는 것! 🎯

---

🚀 문제 해결 핵심 전략

• 최대한 빠르게 증가 → 복제(*2) 마법을 활용
• 마지막에 부족한 개수만 + 연산으로 조정
• 그리디 알고리즘 (Greedy Algorithm)

---

📌 요약

1. 처음에 한 마리만 생성 (current = 1)
2. 복제(*2)를 최대한 활용하여 목표치(N)에 근접
3. 마지막에 +를 사용하여 정확히 N에 맞춤