지우개( BOJ 21756 )

문제 : https://www.acmicpc.net/problem/21756

21756번: 지우개

 

문제 파악하기

기본적인 구현 문제입니다. 각 숫자의 특징을 파악해서 해결할 수도 있고, 큐 혹은 배열을 사용하여 해결하는 방법도 있습니다.

 

문제 해결하기

우선 자료구조(큐, 배열 등...)를 사용하는 방법에 대해 살펴봅시다. 이렇게 직접 숫자들을 가지고 매 작업을 시뮬레이션하기 위해서는 동일한 자료구조 2개가 필요합니다. 각각은 현재 값이 저장된 공간과 새롭게 값을 저장할 공간을 의미하며, 홀수 번째 값은 없애고 짝수 번째 값은 저장하며 1개의 값만이 남을 때까지 반복하면 문제를 해결할 수 있습니다.

 

숫자의 특징을 생각하는 방법도 있습니다. 숫자들은 홀수 번째 위치하는 순간 없어집니다. 이는 자신을 구성하고 있는 약수 중 어느 하나라도 홀수가 있다면 결국에는 없어진다는 의미입니다. 그렇다면 홀수 없이 짝수로만 이루어진 숫자가 마지막에 남게 된다는 사실은 눈치챌 수 있습니다. 바로, 2의 거듭제곱 숫자들을 의미합니다. 물론 모든 2의 거듭제곱 숫자가 남는 것은 아닙니다. 마지막에 남는 숫자는 바로 N보다 작은 가장 큰 2의 거듭제곱 숫자입니다. 그 외의 2의 거듭제곱 숫자들은 서서히 왼쪽으로 이동해서 마지막에는 가장 첫 번째 숫자가 되어 사라지게 됩니다.

 

소스코드

// 자료구조(큐) 사용
#include <stdio.h>
#include <queue>
using namespace std;
 
int N, s;
queue< int > q, tmp;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) q.push(i);
 
    while(q.size()>1) {
        // tmp에 옮겨 담기
        while(!q.empty()) {
            tmp.push(q.front());
            q.pop();
        }
 
        // 홀수 숫자 제거하기
        s = 1;
        while(!tmp.empty()) {
            if(s%2 == 0) q.push(tmp.front());
            tmp.pop();
            
            s++;
        }
    }
    
    printf("%d", q.front());
}

 

// 반복문
#include <stdio.h>
 
int N, ret;
 
int main() {
    scanf("%d", &N);
 
    for(ret=1;ret<=N;ret*=2);
 
    printf("%d", ret/2);
}

후기

여러 가지 방법으로 해결할 수 있는 문제입니다. 정보 올림피아드를 처음 준비하는 학생들에게 추천하고 싶은 문제입니다. 반복문을 배운 학생들에게도 충분히 추천할만한 문제라고 생각합니다.