[백준] 구현 21756번: 지우개

문제

 $N$개의 칸에 $1$ 부터 $N$ 까지의 수들이 왼쪽부터 순서대로 저장되어 있다. 또, 각 칸은 왼쪽부터 $1$ 부터 $N$까지 순서대로 번호가 붙어 있다. 즉, 처음에는 각 칸의 번호와 각 칸에 저장된 수가 같다.

아래 그림은 $N = 7$일 때의 예이다.

다음 작업을 수가 정확히 하나가 남을 때 까지 반복한다.

(A) 홀수번 칸의 수들을 모두 지운다 (B) 남은 수들을 왼쪽으로 모은다.

제일 첫 작업의 (A) 단계가 끝나면 칸들의 상태는 다음과 같을 것이다.

(B) 단계가 끝나면 다음과 같을 것이다.

두번째 작업이 진행되면 칸들은 아래 두 그림과 같이 바뀔 것이다.

이제 수가 하나 남았으므로 작업은 더 이상 진행되지 않는다.

 $N$을 입력으로 받아 위와 같이 작업을 진행했을 때 마지막으로 남는 수를 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 $N$이 주어진다.

출력

마지막으로 남는 수를 한 줄에 출력한다.

Approach

벡터에 1부터 n까지의 수를 넣고 저장 후 벡터의 사이즈가 1이 될 때까지 벡터의 홀수 인덱스에 있는 수들를 새로운 벡터에 업데이트

• n개의 수를 담는 벡터 정의
• 벡터의 홀수 인덱스에 있는 수들을 newvec에 저장
• 오리지널 벡터를 newvec로 update
• newvec을 비움
• 2~3번을 오리지널 벡터의 사이즈가 1이 될 때까지 반복

Source Code

#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;

int main() {
    
    // n입력받기
    int n;
    cin >> n;
    vector<int> v; // 벡터 정의 
    
    // n개의 수를 벡터에 저장
    for (int i = 1; i <= n; i++)
    {
        v.push_back(i);
    }
    
    // newvec 선언
    vector<int> newvec;
    while (v.size() > 1) // 벡터의 사이즈가 1이 될때까지 
    {
        for (int j = 0; j < v.size(); j++)
        {
            if (j % 2 != 0)
            {
                newvec.push_back(v[j]); // 홀수 인덱스에 있는 수들을 newvec에 저장
            }
        }
        v = newvec; // 벡터 업데이트
        newvec.clear(); // newvec 비워주기
    }
    
    // 가장 왼쪽 수 출력 (답)
    cout << v[0] << endl;
    
    return 0;
}

내 머리는 장식인가... 처음에 배열로 풀려다가 안되서 stl vector를 썼다. 진작 쓸걸...