백준 #7481 ATM놀이

문제 링크

[7481 ATM놀이]

문제 설명

자연수 $a, b, k$에 대하여 $ax + by=k$를 만족하는 $(x, y)$중에서 $x+y$가 최소가 되는 순서쌍 $(x, y)$를 구하는 문제

코드

import sys
input = sys.stdin.readline


T = int(input())
for _ in range(T):
    a, b, S = map(int, input().split())
    flag = False
    if a < b:
        a, b = b, a
        flag = True
    if S < b:
        print("Impossible")
        continue
    big = S // a
    S -= big * a
    if S % b == 0:
        if flag:
            print(S // b, big)
        else:
            print(big, S // b)
    else:
        if big == 0:
            print("Impossible")
            continue
        res = [False] * b
        for i in range(1, big + 1):
            S += a
            x = S % b
            if res[x]:
                print("Impossible")
                break
            else:
                res[x] = True
            if x == 0:
                if flag:
                    print(S // b, big - i)
                else:
                    print(big - i, S // b)
                break
        else:
            print("Impossible")

풀이

먼저 큰값으로 나누어 준 뒤에 남은 값에대가 큰값을 하나씩 더해가면서 작은 값으로 나누어 떨어지는지 구했다. 많은 시행착오가 있었는데 나머지는 순환한다는 사실을 다시한번 일깨워준 문제였다..ㅎㅎ