[99클럽/코딩테스트 챌린지/C++] 최소 행동 횟수로 원하는 고양이 수 만들기

문제 설명

마법소녀 마도카는 고양이를 매우 좋아해 마법으로 고양이 N 마리를 키우고자 한다. 처음에는 고양이가 한 마리도 없으며, 아래 두 가지 마법을 사용하여 고양이를 늘릴 수 있다:

1. 생성 마법: 고양이 한 마리를 생성한다.
2. 복제 마법: 현재 집에 있는 고양이 수를 복제할 수 있다. 만약 현재 고양이가 k마리 있다면, 0마리 이상 k마리 이하를 추가로 만들 수 있다.

목표는 이 두 마법을 사용해 최소 행동 횟수로 정확히 N 마리의 고양이를 만드는 것이다.

접근법

처음에는 그리디 알고리즘으로 접근해야 한다는 점을 깨닫지 못했지만, 문제를 분석하면서 각 단계에서 최적의 선택을 하는 것이 필요하다는 점을 알게 되었다.

이 문제를 그리디 알고리즘으로 풀어야 하는 조건들은 다음과 같다:

 

1, 각 단계에서 최적의 선택: 고양이 수가 빠르게 늘어나는 것이 유리하므로, 항상 최대한 빨리 N에 도달할 수 있는 방법을 선택한다.

 

2, 복제 마법의 특징: 두 배로 증가하는 특성 때문에 빠르게 고양이 수를 늘릴 수 있다. 따라서 필요한 경우마다 복제 마법을 활용하고, 그렇지 않은 경우 생성 마법을 사용하는 것이 효과적이다.

코드 설명

#include <iostream>
#include <vector>


using namespace std;
long long Count = 1;
long long Current = 1;

int main() {
    long long N = 0;
    
    std::cin >> N;
    if (N == 0)
    {
        std::cout << N << '\n';
        return 0;
    }
    while (Current != N)
    {
        long long left = N - Current;
        if(left > 1)
        {
            Current += (Current < left ? Current : left);
        }
        else
        {
            Current += 1;
        }
        Count++;
    }

    std::cout << Count << '\n';
    return 0;
}

 

1, 변수 설명:

• Count: 현재까지의 행동 횟수를 저장하는 변수.
• Current: 현재 집에 있는 고양이 수를 나타냄.

2, 로직 설명:

• N이 0인 경우, 곧바로 0을 출력하고 종료.
• 그렇지 않은 경우, Current가 N이 될 때까지 반복하여 복제 또는 생성 마법을 선택하며 고양이 수를 늘린다.
• Current가 N과 같아지면 행동 횟수인 Count를 출력한다.

배운 점

이번 문제를 통해 다음과 같은 점을 배웠다:

 

1, 그리디 알고리즘의 조건을 파악하는 능력: 문제를 풀면서 현재 선택이 전체 최적 해를 보장할 수 있는지 판단하는 기준을 익힐 수 있었다.

 

2, 최적의 선택을 통한 문제 해결: 각 단계에서 최적의 선택을 하는 것이 전체 해결에 얼마나 효율적인지 이해할 수 있었다.

결론

이 문제는 그리디 알고리즘으로 접근하여 최소한의 행동으로 원하는 고양이 수에 도달하는 최적 경로를 찾는 문제였다. 이번 경험을 통해 그리디 알고리즘이 효과적인 상황을 더욱 쉽게 판단할 수 있게 되었고, 이러한 경험을 바탕으로 앞으로도 그리디 알고리즘을 활용할 수 있는 문제를 효율적으로 해결할 수 있을 것이다.