[Python] 백준 3955 캔디 분배 (확장 유클리드 알고리즘)

백준 3955 캔디 분배

 

🍏 유클리드 호제법 설계

• C : 한 봉지의 사탕 개수, K : 사람 수
• x = 1 인당 먹을 사탕 개수
• y = 구매해야할 사탕 개수
• Kx + 1 = Cy 를 만족하는 y를 찾는 것이다.
• 확장 유클리드 호제법에 맞게 식을 수정하면, Cy - Kx = 1 을 만족하는 y를 찾는 것이다.
• 유클리드 호제법에서 a = C, b = -K, 1 = g이다.

 

🍍 예외 처리

1. g = 1 이어야 하기 때문에 gcd(C, K) == 1 이어야 한다.
2. K와 C의 gcd가 1이 아니라면 IMPOSSIBLE
3. 구한 y가 10^9보다 크면 IMPOSSIBLE
4. C == 1 일 때, 사탕 한 봉지에 사탕 한 개만 들었으니까 사람수 + 1만큼 사탕을 사면 된다. 따라서 답은 K+1 이고, K+1 > 10^9라면 IMPOSSIBLE
5. K == 1 일 때, 사람이 한 명이니까 한 봉지만 사고 C-1개의 사탕을 먹으면 된다.→ K=1, C=1인 경우는 사탕을 K+1 봉지 사야한다.
6. → 따라서 4번 처리를 5번 처리 이전에 해줘야 한다.
7. → 단, K=1, C=1일 경우는 0이 된다.
8. ee 함수 내에서 t0 값이 음수가 나올 수 있는데 y값은 항상 양수여야 한다.
9. → 아래 두 가지 처리 중 한 가지를 해주면 된다.

# 1 if t0 < 0: t0 += K # 2 t0 = (t0 % K + K) % K

 

🍅 전체 코드

# 확장 유클리드 호제법 구현
def ee(a, b, K):
    s0 = 1
    s1 = 0
    t0 = 0
    t1 = 1
    while b!= 0: 
        q = a//b
        r = a%b;
        a = b
        b = r
        s = s0 - q*s1
        t = t0 - q*t1
        s0 = s1
        s1 = s
        t0 = t1
        t1 = t
    # (t0 % K + K) % K : t0가 음수 임을 방지
    # if t0 < 0: t0 += K 와 같은 값이다.
    t0 = (t0 % K + K) % K
    # 유클리드 호제법에서 b==0 일 때 a는 gcd
    if a != 1 or t0 > 10**9:
        return 'IMPOSSIBLE'
    return t0

t = int(input())
for i in range(t):
    K, C = map(int, input().split())
    # K, C가 1일 때 예외 처리
    if C == 1:
        if K+1 > 10**9:
            print('IMPOSSIBLE')
        else:
            print(K+1)
        continue
    if K == 1:
        print(1)
        continue
    answer = ee(K, C, K)
    print(answer)