[백준 3343] 장미

🥕 [ 백준 3343 ] 장미

문제 링크

url : https://www.acmicpc.net/problem/3343

 

🍒 문제 분석

묶음 A : a개를 번들로, b 가격

묶음 B : c개를 번들로, d 가격

 

N개를 구매하려고 한다. N개보다 더 사도 좋으니 경제적인 구매를 하시오.

 

🍓 내 해결 과정 ( 틀린 코드 )

- 최소 공배수로 나눠지는 부분은 효율적인 번들로 바로 구매해버리고, 나머지 값에 대해 브루트포스

 

"""
a와 b의 공배수에 대해서는 무조건 effi_bundle로 사는게 이득

ineffi_bundle로 사야할 때가 있을까?
=> effi_bundle로 살 경우, 불필요하게 물건을 추가 구입하는경우

그렇다면 구매는 어떻게 해야하냐.
공배수를 lcm이라고 할 때,

n = lcm * number + res

lcm * number에 대해서는 무조건 effi가 사야하고
res에 대해서는 브루트포스를 해야할 것 같음

res % effi_bundle 값이 크다면, 불필요한 소비가 될 가능성이 높다는 것..

"""

# https://www.acmicpc.net/problem/3343
import sys
import math

input = sys.stdin.readline
# a개를 b원에 팔고, c개를 d원에 팔고
n, a, b, c, d = map(int, input().split())


def get_lcm(x, y):
    if x < y:
        x, y = y, x
    for i in range(x, x * y + 1):
        if i % x == 0 and i % y == 0:
            break
    return i


def sol():
    if b / a == d / c:
        if a < c:
            return math.ceil(n / a) * b
        else:
            return math.ceil(n / c) * d
    elif b / a < d / c:
        effi_bundle, effi_price = a, b
        ineffi_bundle, ineffi_price = c, d
    else:
        effi_bundle, effi_price = c, d
        ineffi_bundle, ineffi_price = a, b

    ans = 0
    lcm = get_lcm(effi_bundle, ineffi_bundle)
    res = n % lcm
    ans += ((n - res) // effi_bundle) * effi_price

    # res에 대해 effi_bundle을 0 부터, effi_bundle로만 샀을 때의 가격을
    # 전부 비교해봄
    # i 는 effi_bundle를 사는 갯수, j는 ineffi_bundle 사는 갯수
    min_cost = 1e9
    for i in range(math.ceil(res / effi_bundle) + 1):
        j = math.ceil((res - i * effi_bundle) / ineffi_bundle)
        if j < 0:
            j = 0
            cost = min( min_cost, i * effi_price + j * ineffi_price )
            break
        cost = min( min_cost, i * effi_price + j * ineffi_price )

    ans += min_cost
    return ans


print(sol() % (10**18))

 

결과는 시간 초과...

 

🥑 정답 풀이

- A 번들이 비효율적이라고 할 때, A 번들을 B 번들 개수 만큼 사면 공배수가 됨

- B 번들 개수 이상 사게 되면 비효율적인 소비가 됨

- 따라서 검사해야할 조건은 비효율 번들 0부터 (B 번들 개수 - 1) 까지.

 

# https://www.acmicpc.net/problem/3343
import sys
import math

input = sys.stdin.readline
# a개를 a_p원에 팔고, c개를 c_p원에 팔고
n, a, a_p, c, c_p = map(int, input().split())


def sol(n, a, a_p, c, c_p):
    # c는 효율적인 번들
    if a_p * c < c_p * a:
        a, a_p, c, c_p = c, c_p, a, a_p

    answer = float("inf")

    # i는 비효율적인 a번들 사는 개수
    # 비효율적인 번들을 c개 만큼 살 이유는 없음. 그때는 공배수라서 효율적 번들을 i개 사면 됨.
    for i in range(c):
        # j는 효율적인 c번들 사는 개수
        j = math.ceil((n - i * a) / c)

        # 비효율적 번들만으로 샀는데 N개를 넘어가는 경우 -> stop searching
        if j < 0:
            j = 0
            answer = min(answer, i * a_p + j * c_p)
            break

        answer = min(answer, i * a_p + j * c_p)
    return answer


print(sol(n, a, a_p, c, c_p))

 

🍉 깨달은 점 및 정리

공배수로 푸는 원리는 같았으나, 관점을 바꿔서 풀지 않으면 안되는 문제였다.

1. A 번들을 B번들을 이루는 개수 만큼 사면, 공배수가 된다는 점.

2. 효율적인 번들을 고려하고, 이후 나머지를 비효율적인 번들로 사는 것은 작업을 두번 처리하게 되는데, 그냥 처음부터 비효율적인 번들만을 고려하면 작업을 한번만 처리해도 되게 된다.

3. 비효율적인 번들을 사는 개수의 범위는 효율적인 번들을 이루는 갯수 안에 포함된다. (공배수를 넘어가버리면, 그때부터는 효율적인 번들로 안살 이유가 없기 때문이다.)

5. 비효율적인 번들을 사는 개수를 늘려나가다, N이 음수가 되어버리면 더 이상 고려 안해줘도 되기 때문에 이때는 break으로 포문을 멈춘다.

 

문제에서 답의 범위는 10의 18승을 넘지 않는다고 했는데, 1e9를 써서 오답이 나왔었다.

1e9로 해결 안되는 큰 수가 있을 수 있다고 생각을 못했어가지고 해당 부분을 디버깅하는데 시간을 오래 잡아먹었다.