백준 2164번 [카드2](C++)-yes6686- 티스토리

백준 문제 풀이: 2164 [카드2]

---

문제 링크: https://www.acmicpc.net/problem/2164

문제 설명:

1부터 N까지의 번호가 적힌 카드가 있다. 카드 뭉치의 맨 위에 있는 카드를 버린 뒤, 그다음 맨 위에 있는 카드를 카드 뭉치의 맨 아래로 옮기는 과정을 반복한다. 카드가 한 장 남을 때까지 이 과정을 계속했을 때 남는 카드 번호를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
using namespace std;

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

    // 카드 초기화
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    // 카드 처리
    while (q.size() > 1) {
        q.pop(); // 맨 위 카드 버리기
        q.push(q.front()); // 다음 카드 맨 아래로 이동
        q.pop();
    }

    // 마지막 남은 카드 출력
    cout << q.front() << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 큐(queue)를 이용하여 카드의 순서를 관리합니다.
• 구현 세부사항:
  • 1부터 N까지의 숫자를 큐에 삽입합니다.
  • 큐의 크기가 1이 될 때까지 아래 작업을 반복합니다:
    • 맨 위 카드를 버립니다(q.pop()).
    • 그다음 맨 위 카드를 큐의 맨 아래로 이동합니다.
  • 마지막 남은 카드를 출력합니다.
• 시간 복잡도: O(n)
  • 각 카드가 한 번씩 큐의 맨 위에서 처리되므로 선형 시간 복잡도를 가집니다.

---

결과

이 코드는 큐를 사용하여 카드의 순서를 효율적으로 관리하며, N이 매우 큰 경우에도 빠르게 실행됩니다. 주어진 N에 대해 남은 마지막 카드를 정확히 계산합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!