[백준 | Python] #30193 - 마술 도구

30193번: 마술 도구

문제

사실 지문부터 조금 난해했다. 최대한 간단하게 설명하면,

 

$K$장의 카드에 정수를 각각 $T$개씩 작성하려 한다.

정수들은 $0$ 이상 $N$미만 이고 하나의 카드에 적힌 정수들은 서로 다르다.

그리고 $0\le a<N$인 정수 $a$가 작성된 카드들의 집합을 $S_a$라 하면 $S_a$는 서로 달라야 한다.

$N$이 주어지고 $K$를 최소화하고자 할 때 최소의 $K$와 그 방법을 출력하여라. $T$는 최소화 하지 않아도 된다.

 

음... 더 어렵나? 간단하게 작성하기가 영 쉽지 않다.

 

아이디어

문득 어릴 때 본 마술이 떠올랐다.

출처: [KC인증]생각하는숫자맞히기(A4사이즈) - 칭찬나라큰나라 (chingchanmall.com)

 

마술의 해법은 숫자가 적혀있다고 한 각 카드의 맨 앞의 수를 더하는 것이다.

관객이 36을 떠올렸다면 초록, 보라의 카드에 생각한 숫자가 적혀있다고 말할 것이고 그 카드의 맨 앞의 숫자인 4와 32를 더하면 36이 나온다.

원리는 2진법을 이용하는 것이다. 각 카드의 적힌 숫자들을 2진법으로 표현해보면 각 카드마다 1로 표현되는 공통되는 비트가 있음을 알 수 있다.

 

본 백준 문제처럼 마이너한 문제를 푸는 사람이면 이 정도 아이디어 만으로도 문제를 풀기에 충분한 조언이 됐을 것이다.

나도 그래서 이 마술을 곧장 이 문제에 적용할 수 있을 줄 알았는데 문제가 있었다.

바로 카드의 적힌 숫자의 개수를 통일해야 한다는 것이다.

 

위 마술을 보면 카드에 적힌 숫자의 개수가 차이가 난다.

왜 그럴까?

만약 마술에서 62나 63까지의 수를 사용했다면 모든 카드에 적힌 숫자가 같을 것이다.

하지만 61과 62를 포함하지 않음으로써 비트 111101과 111110에 해당하는 카드에 적힌 수의 개수가 줄어 불균형이 생긴 것이다.

 

그러면 카드의 적힌 수의 개수의 균형을 맞추면서 마술에 사용할 수 있는 카드 6장을 만들 수 있을까?

가능하다. 다만 위 마술처럼 맨 앞의 숫자를 더해 생각한 숫자를 맞히는 건 힘들 수도 있지만.

그 방법은 다음과 같다.

 

1부터 30까지의 수에 0부터 29까지의 수를 대응한다.

31부터 60까지의 수에 34부터 63까지의 수를 대응한다.

이제 x에 y가 대응되었다고 하면, y를 이진수로 나타내어 활성화된 비트의 카드들에 x를 적는다.

예를들어, x=36은 y=39=0b100111에 대응되었으므로 1, 4, 5, 6번째의 카드에 36을 적는 것이다.

 

위 과정을 거치면 모든 카드에는 같은 개수의 수들이 적혀있을 것이다.

어떻게 그렇다고 확신할 수 있는가?

 

바로 대응 시킨 수를 관찰하면 알 수 있다.

작은 수 절반은 0부터 대응시켰고, 큰 수 절반은 63부터 대응시켰다.

대응된 수의 쌍을 잘 묶으면 (0, 63), (1, 62), (2, 61), ..., (29,34)와 같이 묶을 수 있다. 이들은 모두 합이 63이고 이진수로 0b111111이다.

이제 알겠다. 합이 $2^K-1$이 되는 쌍을 $N/2$개 만들면 전체 비트의 개수 K*(N/2)개가 K개의 카드에 고르게 분배될 수 밖에 없는 것이다.

 

이제 구현을 해보자.

 

 

구현

N이 짝수일 때는 위처럼 하면 된다.

단 N이 홀수일 때는 쌍이 되지 않는 수가 하나 남는다.

이는 간단히 해결할 수 있다. N=59라 가정하면,

0~28을 1~29에, 30~58을 34~62에, 29는 0에 대응 시킨다.

애초에 대응을 1과 62부터 시켜버리고 가운데 수는 그냥 신경을 쓰지 않는 것이다.

 

이를 비트 연산을 통해 각 카드에 적절히 작성하면 된다.

 

코드

n = int(input())
k = (n-1).bit_length()
power = 1 << k

# 대응시킬 수. n이 짝수일 때와 홀수일 때 다르게 해야 함.
a_bit = n%2
b_bit = power-1-n%2

cards = [[] for _ in range(k)]

for a in range(n//2):
    b = n - a - 1

    bit = 1
    for card in cards:
        # 대응된 수의 해당 비트가 활성화 되어 있으면 카드에 작성
        if a_bit & bit:
            card.append(a)
        if b_bit & bit:
            card.append(b)
        bit <<= 1

    # 대응 시킬 수 변경
    a_bit += 1
    b_bit -= 1

print(k)
print(n//2)
for card in cards:
    print(*card)