https://www.acmicpc.net/problem/2164
문제 해결 과정
착안
문제의 의도는 큐(queue)나 덱(dequeue) 등의 자료구조를 활용하여 카드를 버리거나 뒤로 넣는 과정을 반복하는 것을 의도한 것 같았지만 문제 내의 규칙성을 찾아 더 효율적으로 해결을 해보고자 하였다.
문제를 처음 봤을 때, 문제를 간단히 해결할 수 있는 규칙성이 존재할 것이라고 추론할 수 있었던 부분은 작은 수의 $N$에 대하여 문제에서 주어진 과정을 수행하면서 대략적으로 아래와 같은 규칙들이 확인되었기 때문이다.
$1, 2, \cdots, N$번 카드에 대하여, 문제에서 주어진 대로 현재의 맨 위 카드를 버리고 그 다음 카드를 카드의 맨 뒤로 다시 집어넣는 것을 하나의 과정 단위로 수행한다고 했을 때 $1$번 카드부터 시작하여 $N$번 카드가 버려지거나 뒤로 집어넣어질 때까지 그 과정을 반복하는 것을 편의상 '카드를 한 바퀴 돈다(ㅋ...)' 라고 표현을 해보면,
- 주어진 카드에 대해 한 바퀴를 돌고 나면 홀수 카드는 반드시 모두 버려진다.
- 카드를 한 바퀴 돌 때마다 절반 또는 절반 갯수보다 하나 적은 수의 카드를 버리게 된다.
- 현재 남은 카드가 홀수 개이면, 카드를 한 바퀴 돌 경우 돌기 전의 카드 순서와 비교해 한 카드가 뒤로 밀린다.
- 현재 남은 카드가 짝수 개이면, 카드를 한 바퀴 돌아도 카드 순서가 밀리지 않고 유지된다.
등과 같은 규칙을 쉽게 확인할 수 있다. 위의 규칙 중에서 세 번째 규칙을 예로 들면, 원래 7장의 카드로 시작할 때의 카드 순서는 1234567이지만 한바퀴 돌고 나면 462가 된다(2번 카드가 4번, 6번보다 뒤로 밀림).
위에서 발견한 규칙을 토대로 추론해낸 사실은 $N = 2^{k}$ ($k$는 $1$ 이상의 자연수)의 형태일 경우, 반드시 마지막에 남는 카드는 $2^{k}$가 된다는 사실이다. 이는 쉽게 증명해볼 수 있는데, 위의 네 번째 규칙에 의해서 카드의 순서가 바뀌지 않으면서 카드의 수가 $2^{k}, 2^{k-1}, \cdots, 8, 4, 2, 1$과 같이 절반씩 카드가 줄어나가기 때문이다.
한편, $2^{k-1} < N \leq 2^{k}$를 만족하는 2 이상의 자연수 $k$에 대하여 다음과 같은 규칙을 확인할 수 있었다(손 계산으로 여러 가지의 경우를 시도해보며 찾은 규칙).
$$N = 2^{k-1} + 1 \Longrightarrow \textbf{Last Card} = 2$$
$$N = 2^{k-1} + 2 \Longrightarrow \textbf{Last Card} = 4$$
$$N = 2^{k-1} + 3 \Longrightarrow \textbf{Last Card} = 6$$
$$\vdots$$
$$N = 2^{k-1} + m \Longrightarrow \textbf{Last Card} = 2m$$
$$\vdots$$
$$N = 2^{k-1} + (2^{k-1} - 1) \Longrightarrow \textbf{Last Card} = 2(2^{k-1} - 1) = 2^{k} - 2$$
$$N = 2^{k-1} + 2^{k-1} = 2^{k} \Longrightarrow \textbf{Last Card} = 2^{k}$$
이러한 규칙이 발견되는 이유를 수학적으로 증명해보고는 싶었는데 정수론 배경 지식이 부족해서인지 실패했다...
구현
위에서 발견한 규칙을 토대로 계산해보면, $N > 1$일 때, $2^{k-1} < N \leq 2^{k}$를 만족하는 2 이상의 자연수 $k$에 대하여 $1 < m \leq 2^{k-1}$($m$은 자연수)일 때,
$$N = 2^{k-1} + m \Longrightarrow \textbf{Last Card} = 2m$$
$$\therefore 2m = 2(N - 2^{k-1}) = 2N - 2^{k}$$
따라서, $2^{k-1} < N \leq 2^{k}$를 만족하는 $2^{k}$의 값을 찾은 다음 위의 식을 이용해 마지막에 남는 카드 번호를 구했다.
* $N = 1$일 때는 답이 1이므로 예외적으로 출력 처리.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, prod = 2;
cin >> N;
if (N == 1)
{
cout << "1\n";
return 0;
}
while (prod < N)
prod *= 2;
cout << 2 * N - prod << "\n";
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 1904번: 01타일 (0) | 2023.05.25 |
---|---|
[Baekjoon] 1717번: 집합의 표현 (0) | 2023.05.24 |
[Baekjoon] 11729번: 하노이 탑 이동 순서 (0) | 2023.05.22 |
[Baekjoon] 4779번: 칸토어 집합 (0) | 2023.05.21 |
[Baekjoon] 24260번: 알고리즘 수업 - 병합 정렬 1 (0) | 2023.05.20 |
댓글