C++로 숫자 제거 후 남은 수열에서 x번째 요소 찾기

두 개의 숫자 n과 x가 주어진 상황을 생각해 봅시다. 칠판에는 처음 n개의 자연수(1부터 n까지)가 차례대로 적혀 있습니다.

i번째(i는 1부터 시작) 연산에서는 칠판에 적힌 수들 중 i번째 위치에 있는 숫자를 지웁니다. 이 과정을 반복하다가 칠판에 남아 있는 숫자의 개수가 i보다 작아지면 제거 작업을 중단합니다. 우리가 구해야 할 것은 바로 이 시점 이후 칠판에 남아 있는 수열의 x번째 숫자입니다.

예제로 이해하기

입력이 n = 69, x = 6이라고 가정해 보겠습니다. 이때 출력은 12가 됩니다.

• 첫 번째 연산(i = 1): 칠판의 첫 번째 숫자인 1을 지웁니다. 남은 수열은 2, 3, 4, ... 입니다.
• 두 번째 연산(i = 2): 남은 수열의 두 번째 숫자인 3을 지웁니다. 남은 수열은 2, 4, 5, ... 입니다.
• 세 번째 연산(i = 3): 세 번째 숫자인 5를 지웁니다.

이런 식으로 홀수가 하나씩 제거되어 결국 칠판에는 짝수만 남게 되며, 남은 수열의 x번째 숫자는 12가 됩니다.

해결 접근 방식

위 과정을 자세히 관찰해 보면 각 연산마다 홀수(1, 3, 5, ...)가 순서대로 제거된다는 규칙성을 발견할 수 있습니다. 따라서 모든 제거 작업이 끝난 후 칠판에는 짝수만 남으며, 그 결과는 다음 한 줄로 표현됩니다.

return 2 * x;

즉, 복잡한 시뮬레이션 없이도 x번째 남은 숫자는 항상 2 × x라는 것을 알 수 있습니다.

C++ 구현 예제

아래 코드를 통해 더 쉽게 이해해 보겠습니다.

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

int solve(int n, int x){
    return 2 * x;
}

int main(){
    int n = 69;
    int x = 6;
    cout << solve(n, x) << endl;
}

입력

69, 6

출력

12

마무리

이 문제는 겉보기에는 매 연산마다 수열이 변하므로 복잡해 보이지만, 패턴을 분석하면 홀수만 제거되고 짝수만 남는다는 단순한 규칙을 발견할 수 있습니다. 덕분에 O(1)의 간단한 계산만으로 정답을 도출할 수 있는 전형적인 수학적 사고 기반 알고리즘 문제입니다.