[백준 C++] 2164번 카드2: 여러가지 풀이법

 

구현으로 풀 수 있는 아주 간단한 문제이다.

 

풀이법 1 : STD 큐로 직접 구현

 

문제의 구조가 큐이므로, 큐를 선언하여 프로세스를 직접 구현한다.

 

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    int n;
    queue<int> q;

    scanf("%d", &n);
    
    for (int i=1;i<=n;i++)
        q.push(i);
    
    while (q.size() > 1)
    {
        q.pop();
        if (q.size() > 1)
        {
            int a = q.front();
            q.pop();
            q.push(a);
        }
    }
    printf("%d", q.front());
    return 0;
}

 

문제의 큐를 직접 선언한 뒤, 큐 명령어를 통해 마지막 카드를 구한다. 하지만 이 방법은 메모리를 많이 차지하고, 시간도 오래 걸린다. 한마디로 비효율적이다. 따라서 다른 방법을 생각해보고자 했고, 한 바퀴를 돌 때마다 10 8 6 4 2의 형태로 한 칸씩 띄어 사라지는 뒤 역정렬 되는 양상이 반복되는 것을 알 수 있었다. 재귀 함수를 사용하면 효율적으로 해결할 수 있지 않을까라고 생각하여 방법을 생각해 봤지만, 도저히 떠오르지 않아 다른 분의 풀이를 좀 참고했다.

 

풀이법 2 : 요세푸스 문제

참고 풀이  : https://velog.io/@error_io/%EB%B0%B1%EC%A4%80-2164-%EC%B9%B4%EB%93%9C2-Python

[백준] 2164 카드2 Python

 

위 글을 꼭 찾아가서 해법을 확인하자.

 

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int card = 2 * (n-pow(2, floor(log2(n))));
    printf("%d", card!=0 ? card : n);
    return 0;
}

 

요약하자면, 카드 수가 2^n개인 경우에는 결과적으로 2^n번째 카드가 남게된다. 따라서 2^n개의 카드가 남도록 카드를 제거하면 남을 카드를 알 수 있다. log를 통해 2^n을 구하고 이를 2개 간격으로 제거하기에 2를 곱하므로, 2*(전체 카드수-2^n)가 식이 된다.

 

훨씬 최적화된 모오습