[백준][Python] 3343 장미 : 최소공배수.

실버1문제치고 N이 1e15에 최대 1e18까지가서 당황.

이분탐색해보려다 메모리 초과났다.

import sys
input = sys.stdin.readline
from collections import deque

def buy_flower(optimal_cost):
    global min_cost
    queue = deque()
    start_price = 0
    flower = 0
    queue.append([start_price,flower])
    while queue:
        cur_price,flower = queue.popleft()
        for flo_cnt,flo_cost in ((A,B),(C,D)):
            if cur_price + flo_cost <= optimal_cost:
                queue.append([cur_price+flo_cost,flower+flo_cnt])
                if flower+flo_cnt>=N:
                    if cur_price + flo_cost < min_cost:
                        min_cost = cur_price + flo_cost
                    return True

N,A,B,C,D = map(int,input().split())

start = 1
end = int(1e18)
answer = 0
min_cost=0
while start <= end:
    mid = (start+end)//2
    if buy_flower(mid) or min_cost<=mid :
        end = mid-1
        answer = mid
    else:
        start = mid +1

print(answer)

 

그래서 최소공배수만큼 미리 계산해주고 남은부분을 계산하는 방식을 차용했다. 하지만 여전히실패.

 

import sys
input = sys.stdin.readline
from math import gcd

N,A,B,C,D = map(int,input().split())
gcd_AC =gcd(A,C)
lcm_AC = gcd_AC*(A//gcd_AC)*(C//gcd_AC)
pre_pass_flowers = (N//lcm_AC)
R_cnt = N%lcm_AC

if B/A < D/C:
    pre_calculated_cost=pre_pass_flowers*B
else:
    pre_calculated_cost=pre_pass_flowers*D
    
# R_cnt
min_cost = float('inf')
# i는 A세트를 사는 번들의 갯수. R_cnt-A*i는 C에서 메꿔야 하는 갯수.
for i in range(R_cnt//A+1):
    if not (R_cnt-A*i)%C:
        cost_to_R = B*i+(D*((R_cnt-A*i)//C))
        if cost_to_R < min_cost:
            min_cost = cost_to_R
    else:
        cost_to_R = B*i+(D*((R_cnt-A*i)//C+1))
        if cost_to_R < min_cost:
            min_cost = cost_to_R

print(pre_calculated_cost+cost_to_R)

최종적으로 가성비가 안좋은쪽을 공배수만큼 할당한 후 나머지를 반대편으로 채우는 방식을 차용했다.

N-Ai가 음수가 됏을때 정지시키는 것도 중요.

import sys
input = sys.stdin.readline

N,A,B,C,D = map(int,input().split())
min_cost = float('inf')
if B/A > D/C:
    for i in range(C+1):
        if N > A*i:
            if (N-A*i)%C==0:
                cost = B*i + D*((N-A*i)//C)
                if cost<min_cost:
                    min_cost = cost
            else:
                cost = B*i + D*(((N-A*i)//C)+1)
                if cost<min_cost:
                    min_cost = cost
        else:
            if B*i<min_cost:
                min_cost = B*i
            break
else:
    for i in range(A+1):
        if N > C*i:
            if (N-C*i)%A==0:
                cost = D*i + B*((N-C*i)//A)
                if cost<min_cost:
                    min_cost = cost
            else:
                cost = D*i + B*(((N-C*i)//A)+1)
                if cost<min_cost:
                    min_cost = cost
        else:
            if D*i<min_cost:
                min_cost = D*i
            break
print(min_cost)