[PS] BOJ 32160 / 숫자 놀이
![[PS] BOJ 32160 / 숫자 놀이](/content/images/size/w2000/2025/09/--------------2--2.png)
문제 링크: https://www.acmicpc.net/problem/32160
애드 혹 문제입니다.
풀이
조금만 생각해보면, 답은 $N-1$ 또는 $N$으로 정해진다는 것을 알 수 있습니다.
답 구하기
칠판에 1부터 N까지의 수를 적고, 수를 지워가며 가장 마지막으로 남는 수가 최대가 되도록 하는 최선의 풀이는 다음과 같습니다:
- 1부터 N-1까지의 수를 인접한 두 수끼리 빼 1로 만든다.
- 1끼리 최대한 빼서 0으로 만든다.
- 0끼리 최대한 빼서 지워낸다.
- 1 또는 0이 하나 남게 되는데, 남는 수를 N에서 뺀 값이 최댓값이다.
- $N mod 4$가 2 또는 3이라면, 1이 하나 남아 최댓값은 $N-1$이 됩니다.
- $N mod 4$가 0 또는 1이라면, 0이 하나 남아 최댓값은 $N$이 됩니다.
증명
1) 합과 차의 홀짝은 같다.
풀이 과정에서, 임의의 두 수 $x, y$를 빼고 $\left x - y \right$로 바꾸는 연산이 있습니다.
이 때, $(x + y) mod 2 \equiv \left x - y \right mod 2$이기 때문에, 두 수의 합과 차의 홀짝은 같습니다.
칠판에 적힌 전체 수의 합이 $S = \sum_{i=1}^{N} i = {N(N+1) \over 2}$인데, 두 수를 빼고 그 차를 넣는 연산을 진행하게 될 경우 합은 다음과 같이 변하게 됩니다.
- 연산 이전: $S_{1} = 1 + 2 + \cdots + x + y + \cdots + N$
- 연산 이후: $S_{2} = 1 + 2 + \cdots + (y - x) + \cdots + N$
두 수의 합과 차의 홀짝이 같으므로, 연산 이전의 전체 수의 합 $S_1$과 연산 이후의 전체 수의 합 $S_2$의 홀짝 또한 같습니다.
2) 칠판에 최종적으로 남는 값의 상한
임의의 두 수 $x, y$를 $\left x - y \right$로 바꾸는 연산에 대해,
$\left x - y \right \leq min(x, y)$입니다.
따라서, 칠판에서 어떤 두 수를 골라 연산을 반복하더라도 최종적으로 남는 수는 $N$ 이하입니다.
3) 최댓값이 N 또는 N-1인 이유?
앞서 1에서 연산 이전과 이후의 전체 숫자 합의 홀짝이 동일하다고 했습니다. 그에 따라, 연산을 반복해 최종적으로 남게 되는 수의 홀짝은 초기 전체 수의 합인 $S = N(N+1) \over 2$와 같습니다.
또, 2에 의해 최종적으로 칠판에 남게 되는 수의 상한은 $N$입니다. 이때, 마지막에 칠판에 남은 수도 결국 연산을 거듭한 뒤의 전체 수의 합이며, 따라서 $S$와 홀짝이 같음을 알 수 있습니다.
이를 통해, $N$과 $S$의 홀짝이 같은지 다른지를 통해 최댓값을 결정하면 됩니다.
- $N$과 $S$의 홀짝이 같은 경우
- 칠판에 남겨진 최댓값은 $N$
- $N$과 $S$의 홀짝이 다른 경우
- 칠판에 남겨진 최댓값은 $N-1$
- $N$과 $S$의 홀짝이 다른데 $S$가 $N$이 될 수 없으므로 $N$ 다음으로 크고 홀짝이 $N$과 반대인 $N-1$이 답이 된다.
해 구성하기
위 과정을 그대로 코드로 구현하면 됩니다.
먼저, 구현의 편의를 위해 칠판에 수를 새로 쓰는 함수와 기존의 수를 지우는 함수를 구현했습니다. 칠판은 숫자를 키, 그 숫자가 칠판에 적힌 개수를 값으로 가지는 Map으로 정의했습니다.
N = int(input())
board = {i: 1 for i in range(1, N + 1)}
def add_to_board(n):
try:
board[n] += 1
except KeyError:
board[n] = 1
def remove_from_board(n):
board[n] -= 1
if board[n] == 0:
del board[n]칠판에 수를 쓰고 지우는 함수들
1) $1 \dots N-1$의 수를 인접한 수끼리 빼 모두 1로 만들기
# Step 1. 1 ... N-1의 모든 수를 인접한 수 끼리 빼서 1로 만든다.
number = N - 1
while number >= 2:
a = number
b = a - 1
if a in board and b in board:
res.append(f"{a} {b}\n")
remove_from_board(a)
remove_from_board(b)
add_to_board(abs(a - b))
number -= 21번 단계의 코드
N-1부터 시작해 인접한 2개의 수를 서로 빼 1로 만드는 과정입니다.
- N이 짝수라면 N-1부터 2까지의 수를 서로 빼고, 1은 그대로 남습니다.
- 이 경우, 1은 ${N - 2 \over 2} + 1$개 존재합니다
- N이 홀수라면 N-1부터 1까지의 수를 서로 뺍니다.
- 이 경우, 1은 ${N - 1} \over {2}$개 존재합니다
2) 1끼리 최대한 빼서 0으로 만들기
# Step 2. 1이 2개 이상 남아있다면, 1을 계속 빼서 0을 만든다.
ones = board.get(1, 0)
if ones > 1:
res.append("1 1\n" * (ones // 2))
board[0] = ones >> 1
board[1] = ones & 1
if board[1] == 0:
del board[1]2번 단계의 코드
1의 개수에 따라 1이 한 개 남을 때도, 모두 0으로 지워질 때도 있습니다.
3) 0끼리 최대한 빼서 0을 1개만 남기기
# Step 3. 0이 있다면, 0을 계속 지운다.
zeros = board.get(0, 0)
if zeros > 1:
res.append("0 0\n" * (zeros - 1))
board[0] = 1
try:
if board[0] == 0:
del board[0]
except KeyError:
pass3번 단계의 코드
0끼리 지우는 경우, 0 2개가 지워지고 0이 1개 다시 생기므로 전체적으로 봤을 때는 연산 1회당 0이 1개 지워집니다. 따라서, (0의 개수 - 1)번 0을 지워야 0을 모두 지울 수 있습니다.
4) 답 구하기
# Step 4. 답 찾기
ans = N
# Step 4-1. 1과 0이 모두 있다면 1만 남겨준다.
if board.get(0, 0) == 1 and board.get(1, 0) == 1:
res.append("1 0\n")
remove_from_board(0)
# 0이 남아있을 경우 답은 N
if board.get(0, 0) > 0:
res.append(f"{N} 0\n")
remove_from_board(0)
# 1이 남아있을 경우 답은 N - 1
elif board.get(1, 0) > 0 and N > 1:
res.append(f"{N} 1\n")
remove_from_board(1)
remove_from_board(N)
add_to_board(N - 1)
ans = N - 1
print(ans)
print("".join(res))4번 단계의 코드
앞서 2번 단계에서 1이 남아있었다면, 3번 단계에서 1개로 줄인 0과 1을 빼서 1을 하나 남긴 뒤 $N$과 1을 뺀 $N-1$이 답이 됩니다.
1이 남아있지 않다면, $N$과 0을 뺀 $N$이 답이 됩니다.
전체 코드
input = open(0).readline
N = int(input())
board = {i: 1 for i in range(1, N + 1)}
res = []
def add_to_board(n):
try:
board[n] += 1
except KeyError:
board[n] = 1
def remove_from_board(n):
board[n] -= 1
if board[n] == 0:
del board[n]
# Step 1. 1 ... N-1의 모든 수를 인접한 수 끼리 빼서 1로 만든다.
number = N - 1
while number >= 2:
a = number
b = a - 1
if a in board and b in board:
res.append(f"{a} {b}\n")
remove_from_board(a)
remove_from_board(b)
add_to_board(abs(a - b))
number -= 2
# Step 2. 1이 2개 이상 남아있다면, 1을 계속 빼서 0을 만든다.
ones = board.get(1, 0)
if ones > 1:
res.append("1 1\n" * (ones // 2))
board[0] = ones >> 1
board[1] = ones & 1
if board[1] == 0:
del board[1]
# Step 3. 0이 있다면, 0을 계속 지운다.
zeros = board.get(0, 0)
if zeros > 1:
res.append("0 0\n" * (zeros - 1))
board[0] = 1
try:
if board[0] == 0:
del board[0]
except KeyError:
pass
# Step 4. 답 찾기
ans = N
# Step 4-1. 1과 0이 모두 있다면 1만 남겨준다.
if board.get(0, 0) == 1 and board.get(1, 0) == 1:
res.append("1 0\n")
remove_from_board(0)
# 0이 남아있을 경우 답은 N
if board.get(0, 0) > 0:
res.append(f"{N} 0\n")
remove_from_board(0)
# 1이 남아있을 경우 답은 N - 1
elif board.get(1, 0) > 0 and N > 1:
res.append(f"{N} 1\n")
remove_from_board(1)
remove_from_board(N)
add_to_board(N - 1)
ans = N - 1
print(ans)
print("".join(res))
solution.py