카드2 (백준-2164번)

1. 손으로 풀어보기

2. 코드 구현하기 1

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int card_game(queue<int> card);


int main(){
    int N;
    cin >> N;
    queue<int> card;
    int result=0;
    
    for(int i=1; i<=N; i++){
        card.push(i);
    }
    result = card_game(card);
    
    cout << result;
}

int card_game(queue<int> card){
    
    card.pop();
    card.push(card.front());
    card.pop();
    
    return card.size() == 1 ? card.front() : card_game(card);
}

문제에 시간 제한과 메모리 제한이 존재해 위 코드는 메모리 제한으로 인해 실패해서 다르게 구현해 보았습니다.

 

3. 코드 구현하기2

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int N;
    cin >> N;
    queue<int> card;
    int result=0;
    
    for(int i=1; i<=N; i++){
        card.push(i);
    }
    
    while(card.size() > 1){
        card.pop();
        card.push(card.front());
        card.pop();
    }
    cout << card.front();
}

재귀함수에서 while문으로 바꿔서 구현하니 메모리 제한에 걸리지 않고 성공하게 되었습니다.

 

참조) Do it! 코딩테스트