[Baekjoon] 2164번: 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

---

 

문제 해결 과정

착안

문제의 의도는 큐(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;
}

 

실행 결과