백준 1214 : 쿨한 물건 구매

https://www.acmicpc.net/problem/1214

1214번: 쿨한 물건 구매

 

해결 방법 : 브루트포스 + (탐색 범위 축소)

• D, P, Q 에 대해, D 이상이 되는 최소의 P*n(n:자연수)을 기준으로 잡고 범위 [0, n-1]에 대해 브루트포스로 탐색하며 P*i(i in [0, n-1]) + Q*m(m:자연수)가 D 이상인 값을 구하면 된다.
  
  • 다만 다음 사항을 이용하여 시간복잡도를 줄일 필요가 있다. (worst case가 10^9 loop이므로..)
    • P를 더 큰 값으로 지정한다. (loop 횟수 축소)
    • 현재까지의 최솟값 answer가 또 다시 나오면 answer 자체가 반복되는 것이므로 loop를 종료한다.
      • 주의할 점이 있는데, loop를 0 to n-1로 잡으면 예외 케이스가 생긴다. 이유를 생각해보면, 만약 주어진 값이 D, P, Q = (51, 6, 9)인 경우, P*n = 54일 것이고, 첫번째 loop에서 P*0 + Q*m 또한 54가 되며 loop가 종료된다. 하지만 6*4 + 9*3 = 51로 best case가 존재한다. 
      • 따라서, 0 to n-1 이 아니라 n-1 to 0로 탐색해주면 공배수로 인한 예외 처리를 따로 해주지 않아도 될 것이다.

import sys
input = sys.stdin.readline

def solution(D, P, Q):
    if D % P == 0 or D % Q == 0: return D

    P, Q = max(P, Q), min(P, Q) # P > Q
    mx_P = D // P + 1 # P*n이 D 이상이 되게끔하는 최소 n 
    answer = P * mx_P # 위의 경우 최소 비용

    for i in range(mx_P-1, -1, -1): # n-1 to 0 탐색
        div, mod = divmod((D - (i * P)), Q) # P*i를 제외한 비용을 Q로 나눈 몫 & 나머지 
        if mod == 0: return D 
        mn_i = (i * P) + ((div + 1) * Q) # i에 대한 최소 비용
        if answer == mn_i: break # answer가 반복되는 경우
        answer = min(answer, mn_i)

    return answer

if __name__ == '__main__':
    D, P, Q = map(int, input().split())
    result = solution(D, P, Q)
    print(result)