D,P,Q = map(int,input().split())
P,Q = max(P,Q),min(P,Q)
MIN = 1e10
for i in range(min(D//P,Q)+1):
MIN = min(MIN,(Q-(D-P*i)%Q)%Q)
MIN = min(MIN,(P-(D%P))%P)
print(D+MIN)재미있는 문제였다.
코드를 보면 알다싶이 매우 간단하게 구현 가능하지만, 아이디어를 떠올리는데 약간의 고민이 필요했다.
알고리즘을 설명하면,
1. 더 큰 수를 P, 더 작은 수를 Q로 둔다.
2. P를 한개도 안낼 때의 금액부터, 한개 낼때, 두개 낼때... 를 for문으로 돌려 지불 가격의 최솟값을 구한다.
3. 이때 for문은 D//P와 Q 중 더 작은 값까지 돌린다. (Q까지 돌리는 이유는 P를 Q번 내면 P로 지불한 금액은 P*Q, 이는 Q의 배수이기 때문에 그 이후의 값은 차이가 없어 반복할 필요가 없다)
4. 모든 금액을 P로만 낼 때의 가격으로 마지막으로 갱신 후, 최솟값을 출력한다.
3번에서 D//P와 Q 중 더 작은 값까지 for문을 돌리는 것이 이 문제 해결의 키 포인트이다. 배수 관계를 고려하여 불필요한 경우는 제거하는 것이다.
여담) 이 문제의 숏코딩 순위 2등이 되었다.