13736. 사탕 분배(파이썬)

문제: 무단 배포 금지로 인해 사이트 주소로 남깁니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BB5d6T7gDFARO

SW Expert Academy

 

코드 이해를 위해 꼭 주석을 읽어주시기 바랍니다.

 

정답 코드:

"""
전체 사탕의 개수는 A+B=C, 일 때 C로 항상 일정하다.
n번째 단계에서 A개를 가지고 있는 사람이 B개를 갖고 있는 사람보다 더 적다면 2A가 되고
A가 B보다 많다면, C-A 개(B)를 A에서 빼게 될 테니 2A-C 가 된다.
- key point:어차피 A가 가지고 있는 사탕의 개수는 C를 넘지 않기 때문에 가지고 있는 사탕의 개수에서 %C를 해도 동일한 값이 나와야 함.
(2A-C) % C 를 하면 ((2A % C) - (C % C))%C 와 동일하고 C %C 는 0이니까 2A % C와 동일.(모듈러 연산)
이를 두 번 반복하면 ((2A % C)2) % C 가 될텐데 정리하면 ((2A %C) ( 2 % C ))%C를 거쳐서 (2^2 A) % C가 된다.

여기서 일반항을 구할 수 있다.
n번째 분배에서 m만큼 A가 B보다 작았다면,
n번째 분배에서의 A가 가지고 있는 사탕의 개수는 2^n*A - 2^(n-m)*C 이고,
이것은 (2^n*A - 2^(n-m)*C) % C와 같으며,
(2^n * A) % C 가 된다.
-------------------------------------

거듭제곱 계산에서 a의 1024제곱을 구할 때 a x a x a x a x a x a .......
의 방법으로 한다면 1024 즉 n번의 시간이 필요하지만
(a^512) * (a^512).... 처럼 a를 512번 곱하고 이 수를 서로 곱해주면 계산이 절반이 줄어드는 방식을 이용하면
X의 n제곱 수를 구하는데 필요한 시간복잡도를 O(log n)으로 줄일 수 있다. -> 재귀 함수 또는 루프

"""

def power(a,k,s):
    result = 1
    while k > 0:
        if k % 2 != 0:
        #마찬가지로 모듈러 연산에 의해, % s 해도 같은 값이 됨
            result = (result * a) % s
        k //= 2
        a = (a * a) % s

    return result


T = int(input())
for test_case in range(1, T + 1):
    A, B, K = map(int, input().split())
    S = A + B
    # Ak = ((2**K)*A) % S K 만큼의 시간이 걸림 -> log n까지 줄여야 함.
    Ak = power(2, K, S) * A % S
    Bk = S - Ak
    answer = min(Ak, Bk)

    print(f"#{test_case} {answer}")

 

 

모듈러 연산 참고 자료: https://zhelddustmq.tistory.com/63