[BOJ][🟡3][백준#01341] 사이좋은 형제

문제 출처

BAEKJOON Online Judge #1341

문제

영식이와 민식이는 케이크를 나누어 먹으려고 한다. 일단 영식이가 절반을 먹고, 민식이가 남은 절반을 먹는다. 또 계속 이렇게 절반을 먹고 한다. 이렇게 무한번 하고 나면 결국 케이크를 다 먹게 된다. 표로 만들어 보면 다음과 같다.

영식 민식

1/2 1/4

1/8 1/16

1/32 1/64

1/128 1/256

… …

위와 같이 먹게 되면 영식이는 항상 민식이의 두 배를 먹게 되므로 케이크의 2/3을 먹게 되고, 민식이는 1/3을 먹게 된다. 케이크를 재미있게 먹기 위해서 여러 가지 패턴을 만들기로 했다. 그렇게 되면 영식이가 먹게되는 케이크는 달라지게 된다. 만약 “영식,민식,영식”과 같이 먹게되면 다음과 같이 먹는다. 이렇게 되면 영식이는 5/7을 먹게 된다. 영식이가 먹게되는 케이크의 양이 분수로 주어진다. 그때, 패턴을 출력하는 프로그램을 작성하시오.

영식 민식 영식

1/2 1/4 1/8

1/16 1/32 1/64

1/128 1/256 1/512

입력

첫째 줄에 두 정수 a와 b가 주어진다. a와 b는 a/b에서 분자와 분모다.

출력

첫째 줄에 먹는 패턴을 출력한다. 패턴은 영식은 *로, 민식은 -로 출력한다. 만약, 패턴의 길이가 60 이하인 것이 없으면 -1을 출력한다. 가능한 패턴이 여러 가지이면 짧은 것을 출력한다.

제한

0 ≤ a ≤ b ≤ 263-1 a와 b는 서로소

예제

예제 1

입력

2 3

출력

*-

예제 2

입력

5 7

출력

*-*

예제 3

입력

0 1

출력

-

예제 4

입력

5 9

출력

*---**

예제 5

입력

1 2

출력

-1

예제 6

입력

76861433640456464 76861433640456465

출력

********************************************************----

My Sol

def make_mothers():
    global MAXX
    mothers = []
    n = 2
    while n < MAXX:
        mothers.append(n - 1)
        n *= 2
    return mothers


def make_ab(mothers):
    global MAXX
    a, m = map(int, input().split())
    for mother in mothers:
        if not mother%m:
            sq = mother//m
            aa = a*sq
            bb = mother - aa
            return aa, bb
    return 0

def is_odd(n):
    return n%2


def main():
    mothers = make_mothers()
    ret = make_ab(mothers)
    if not ret: return -1
    a, b = ret

    ans = ''
    while a or b:
        if a and is_odd(a):
            if is_odd(b): return -1
            ans = '*' + ans
            a-=1

        elif b and is_odd(b):
            if is_odd(a): return -1
            ans = '-' + ans
            b-=1

        else: return -1

        a, b = a//2, b//2

    return ans if len(ans) <= 60 else -1

MAXX = 2**65
print(main())

까다로운 문제였다.

1. 서로소로 만들어주기 위한 나누기 이전의 분모의 경우 2**n-1의 형태이다. 이를 mothers에 차례대로 넣는다.
2. 입력으로 a와 m을 받고, m이 mothers 내에 떨어지는 가장 작은 수 mother를 찾는다. 해당 mother을 분모로 하도록 a와 b를 구성해 반환한다.
3. 이 a와 b는 홀수 또는 짝수로 교차해야 한다. 마지막에 더해진 사람이 1이고 그 이전에는 2씩 곱하며 더하는 방식이기 때문이다. 분수의 특성상 분모가 2배씩 커지면 값은 2배씩 작아지므로, 마지막에 1을 더하기 위해서 이전의 값들은 매번 2배로 곱하는 것이다.
4. 이 성질을 이용해 홀수인 수를 판단하여 짝수처리하고 2로 나누며 같은 작업을 반복하면 되갰다. 뒤부터 처리하는 것이다.

결과

맞았습니다!!