[algorithm] 백준 2164번 카드2

 

1부터 N까지의 원소가 담긴 큐를 설정하고

큐의 남은 원소가 1개가될때까지

홀수 번째 때 맨 앞 원소를 버리고 

짝수 번째 때 맨 앞 원소를 맨 뒤로 옮기는 작업을 반복하므로

count 변수를 설정해서

count가 짝수일 때와 홀수일 때로 나눠서 풀었다

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int n;
    cin >> n;
    int count = 1;
    int p;
    queue<int> q;
    
    for(int tmp=1; tmp<n+1; tmp++)
        {
            q.push(tmp);
        }

    while(1)
        {
            if(q.size() == 1) break;
            else
            {
                if(count%2 == 1)
                {
                    q.pop();
                }
                else
                {
                    p = q.front();
                    q.push(p);
                    q.pop(); 
                }
                count++;
            }
        }
    cout << q.back();
    return 0;
}

 

홀수번째 때와 짝수번째 때로 굳이 나누지 않고

두 작업을 한번의 작업으로 생각해서 푸는 방법도 있었다

// Authored by : OceanShape
// Co-authored by : -
// http://boj.kr/de9183460fa945a69e8692510b3fd803
#include <bits/stdc++.h>
using namespace std;

int N;
queue<int> q;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  for(int i = 1; i <= N; ++i) q.push(i);
  while(q.size() != 1){
    q.pop();
    int tmp = q.front();
    q.push(tmp);
    q.pop();
  }
  cout << q.front();
}

이렇게하면 굳이 count 변수 설정할 필요 없이

조금 더 간단하고 효율적이게 풀 수 있다