문제
두 종류의 지폐 a원과 b원으로 정확히 S원을 만들 수 있는 장 수 조합을 구하라. 불가능하면 Impossible을 출력한다.
입력
테스트 케이스 수 T, 각 케이스에 a, b, S가 주어진다.
출력
각 케이스마다 a원 장 수와 b원 장 수를 출력하거나 Impossible을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 5 16 | 2 2 |
풀이
큰 지폐를 최대한 사용하고 나머지를 작은 지폐로 채울 수 있는지 확인한다.
- a와 b 중 큰 값을 기준으로 최대 사용 수부터 줄여간다
S - 큰지폐*수가 작은 지폐로 나누어떨어지면 해를 찾은 것이다- 비둘기집 원리에 의해 최대
min(a, b) + 1번만 시도하면 된다
핵심 아이디어: 한 지폐의 수를 고정하면 나머지가 다른 지폐로 나누어떨어지는지 확인하는 문제가 되며, 나머지의 주기성으로 유한 횟수 내에 판별 가능하다.
코드
T = int(input())
for i in range(T):
a, b, S = map(int, input().split())
sw = 0
if b < a:
sw = 1
b, a = a, b
ans = 0
t = S // b * b
for j in range(a + 2):
if (S - t) % a == 0:
ans = [(S - t) // a, t // b]
break
else:
t -= b
if ans == 0 or ans[0] < 0 or ans[1] < 0:
print("Impossible")
else:
if sw == 1:
ans.reverse()
print(*ans)복잡도
- 시간: O(min(a, b)) (케이스당)
- 공간: O(1)