[백준 1341] 사이좋은 형제

1341번: 사이좋은 형제

알고리즘 : 수학, 구현

난이도 : 골드Ⅲ

 

1. 문제요약

• 영식이와 민식이가 순서를 정하여 현재 케이크의 절반씩 먹는데, 이를 무한히 반복하면 케이크를 다 먹게 된다.
• 케이크를 다 먹은 후 영식이가 먹게 된 케이크의 비율을 전체의 $\frac{a}{b}$라고 하자.
• 입력으로 $2^{63}-1$이하의 서로소인 a,b가 주어질때, 영식이와 민식이가 케이크를 먹은 패턴을 출력해야 한다. 영식이가 먹은 경우를 '*', 민식이가 먹은 경우를 '-'로 나타낸다. 다만 패턴의 길이가 60이하인 것이 없으면 -1을 출력하고, 가능한 패턴이 여러가지 이면 짧은 것을 출력한다.
• 예를 들어, 입력으로 5 7 이 주어지면 영식이와 민식이가 먹은양의 비율은 5:2가 된다. 그리고 이 비율은 반복되는 패턴 전부에서 생각할 필요는 없고 단위 패턴에서만 고려해도 된다. 따라서 예시의 비율은 $\frac{1}{2}+ \frac{1}{8}: \frac{1}{4}$과 동일하기 때문에, 영식이와 민식이는 *-* 패턴으로 반복해서 케이크를 먹었음을 알 수 있다.

2. 아이디어

• 예를들어 영식-민식-민식-민식-영식-영식 패턴으로 먹었다고 가정해 보자. 패턴의 길이는 7임을 기억하자.
• 이 경우 영식이와 민식이가 먹은 비율은 $ \frac{1}{2} + \frac{1}{32}+ \frac{1}{64} : \frac{1}{4}+ \frac{1}{8}+ \frac{1}{16} = 5:4$가 된다. 이 경우 a,b는 5 9 로 주어지게 된다.
• 영식의 입장에서, 패턴중 자기가 먹은 경우를 1로 표현하면 이진수 100011이 되고 이는 35이다.
• 민식의 입장에서는 이진수 011100이 되고 이는 28이다. 이는 각자 먹은 비율과 일치하는 값들이다.
• 9를 이진수로 변환하면 1001이 되고, 이는 7개의 1로 이루어진 이진수 111111, 즉 $2^7-1=63$의 약수이다.
• 즉 이 문제의 핵심을 정리하면, 주어진 b가 'x개의 1로 이루어진 이진수'의 약수가 된다면 길이 x의 패턴이 존재하게 된다는 점이다.

3. 구현과정

• a,b를 입력 받는다.
• 인자 i에 대해 1부터 60까지 순회하면서 b가 $2^i-1$의 약수가 되는 경우를 찾고, 이때 b로 나눈 몫을 factor에 저장한다. 만약 범위안에 이러한 i가 없다면 패턴의 길이가 60보다 커지게 되므로 -1을 출력하고 프로그램을 종료시킨다.
• 주어진 a,b에 factor를 곱한 수를 이진수로 변환시켜 각각 abin, bbin에 저장한다.
• 만약 abin의 길이가 bbin보다 작은 경우라면 민식이가 먼저 먹게 되어 패턴이 0으로 시작하게 되는 경우이다. 이 0이 abin에 나타나있지 않기 때문에 abin 앞에 빠져있는 개수만큼 0을 붙여준다.
• 이제 abin을 순회하면서, 1이 나타나면 영식이가 먹은 경우이므로 *를, 0이 나타나면 민식이가 먹은 경우이므로 -를 출력시키면 된다.

4. 파이썬 코드

a,b = map(int,input().split())

for i in range(1, 61):
    if (2**i - 1) % b == 0:
        factor = (2**i - 1) // b
        break
else:
    print(-1)
    exit()

abin, bbin = bin(a*factor)[2:], bin(b*factor)[2:]
if len(abin) < len(bbin):
    abin = '0' * (len(bbin) - len(abin)) + abin
for i in abin:
    print('*' if i == '1' else '-', end='')