BOJ 3955 캔디 분배

2 min read
On this page
  1. 문제
  2. 복잡도 분석
  3. 접근법
  4. 풀이
  5. Code Review
  6. 유사 문제 추천

문제

캔디 분배 https://www.acmicpc.net/problem/3955

각 봉지에 KK개의 사탕이 들어있을 때, yy봉지를 사서 XX명에게 xx개씩 나누어주고 1개가 남도록 하는 최소의 양의 정수 yy를 구하는 문제. (단, y≤109y \le 10^9이며 x>0,y>0x > 0, y > 0)

복잡도 분석

  • time complexity : O(log⁡(min⁡(K,C)))O(\log(\min(K, C))) - 확장 유클리드 호제법의 시간 복잡도를 따르며, 최대 100개의 테스트 케이스를 제한 시간(1초) 내에 매우 여유롭게 통과함.
  • space complexity : O(log⁡(min⁡(K,C)))O(\log(\min(K, C))) - 재귀 호출에 의한 Call Stack 메모리만 사용하며, 추가적인 자료구조 불필요.

접근법

  1. C⋅y−K⋅x=1C \cdot y - K \cdot x = 1 형태의 베주 항등식(Bézout’s Identity)으로 문제를 재구성.
  2. 확장 유클리드 알고리즘(Extended Euclidean Algorithm)을 사용하여 특수해와 gcd⁡(K,C)\gcd(K, C)를 도출.
  3. gcd⁡≠1\gcd \neq 1인 경우 해가 존재하지 않으므로 예외 처리.
  4. yy를 양수로 보정하기 위해 y=(y(modK)+K)(modK)y = (y \pmod K + K) \pmod K 적용.
  5. “친구들에게 사탕을 나누어 준다(x>0x > 0)“는 물리적 제약 조건을 만족하기 위해 C⋅y≤1C \cdot y \le 1인 경우 yy에 KK를 가산.
  6. 최종 yy가 상한선(10910^9)을 초과하는지 검증.

풀이

import sys
input = sys.stdin.read

inp = input().replace('\x1a', '').splitlines()

def egcd(a,b):
    if b==0:
        return (a,1,0)
    g,x1,y1= egcd(b,a % b)
    x = y1
    y = x1 - (a//b) * y1
    return (g,x,y)

def solv(k,c):
    # c*y = k*x + 1
    # c*y - k*x = 1
    # (-k) * x + c * y = 1
    g,x,y = egcd(k,c)
    y = (y%k + k) %k

    # c*y가 1 이하라면 x가 0이하가 되어버린다.. 1 1 때문에 while
    while c*y <= 1:
        y+=k

    if g != 1 or (y>1e9): 
        print("IMPOSSIBLE")
        return
    print(y)

for i,x in enumerate(inp):
    if i>0:
        a,b = map(int, x.split())
        solv(a,b)

Code Review

  • 수학적 모델링의 현실화: 수식적인 정답을 구하는 것에 그치지 않고, while c*y <= 1 루프를 도입해 실제 세계의 분배 조건(x>0x>0)을 우아하게 해결한 점이 매우 훌륭함.
  • 부동소수점 오차 방지: 경계값 검사 시 실수형 1e9 대신 완벽한 정수 비교를 위해 10**9를 사용하는 것이 안전함.

유사 문제 추천

  • 잉여역수 구하기 (BOJ)
  • 확장 유클리드 알고리즘 (BOJ)
  • 계산기 프로그램 (BOJ)
  • 선형 연립 합동식 (BOJ)
  • 사과나무 (BOJ)
Discussion

Comments