[백준] 1049 - 기타줄

www.acmicpc.net

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

🖥 시작하며

그리디 구현 문제다. 여러 가지의 조건이 존재하므로 잘 판단해야 한다.

중요한 부분은 브랜드를 교차해도 된다는 사실이다. 처음에 이거 고려 안했다가 틀렸다. 이를 통해 그냥 브랜드별 패키지, 낱개 최솟값을 가져오는 것부터 시작해야 유리하다.


# 모든 브랜드 중 패키지 최소 가격과 낱개 최소 가격 선택
brand_cost_6 = min(brand, key=lambda x: x[0])[0]  # 패키지(6개) 최소 가격
brand_cost_1 = min(brand, key=lambda x: x[1])[1]  # 낱개 최소 가격

최소 가격들을 가져온다.

이후 조건을 붙여 차근차근 풀어준다.


# 기타줄이 6개 미만
if N < 6:
    # 패키지 구매 vs 낱개 구매 중 선택
    res = min(brand_cost_6, brand_cost_1 * N)
# 기타줄이 6개 이상
else:
    tmp_6 = N // 6  # 패키지 수
    tmp_1 = N % 6  # 낱개 수

    # 패키지로만 구매 vs 낱개로만 구매 중 선택
    res = min(brand_cost_6 * tmp_6, brand_cost_1 * tmp_6 * 6)
    # 남은 낱개에 대해
    # 패키지 구매 vs 낱개 구매 중 선택
    res += min(brand_cost_6, brand_cost_1 * tmp_1)

기타줄이 6개 미만인 경우

패키지를 구매하는 것과 낱개를 기타줄 개수만큼 구매하는 것 중 어느 것이 유리한지 판정해야 한다.

기타줄이 6개 이상인 경우

우선 패키지 묶음 개수와 낱개 개수를 나눈다.
이후 패키지로만 구매하는 것과 낱개를 기타줄 개수만큼 구매하는 것 중 어느 것이 유리한지 판정한다.
남은 낱개에 대해서도 판정한다.

⚙️ 코드


import sys

input = sys.stdin.readline

if __name__ == "__main__":
    # N : 기타줄의 개수, M : 브랜드의 수
    N, M = map(int, input().split())
    brand = []
    res = 0

    for _ in range(M):
        cost_6, cost_1 = map(int, input().split())
        brand.append([cost_6, cost_1])

    # 모든 브랜드 중 패키지 최소 가격과 낱개 최소 가격 선택
    brand_cost_6 = min(brand, key=lambda x: x[0])[0]  # 패키지(6개) 최소 가격
    brand_cost_1 = min(brand, key=lambda x: x[1])[1]  # 낱개 최소 가격

    # 기타줄이 6개 미만
    if N < 6:
        # 패키지 구매 vs 낱개 구매 중 선택
        res = min(brand_cost_6, brand_cost_1 * N)
    # 기타줄이 6개 이상
    else:
        tmp_6 = N // 6  # 패키지 수
        tmp_1 = N % 6  # 낱개 수

        # 패키지로만 구매 vs 낱개로만 구매 중 선택
        res = min(brand_cost_6 * tmp_6, brand_cost_1 * tmp_6 * 6)
        # 남은 낱개에 대해
        # 패키지 구매 vs 낱개 구매 중 선택
        res += min(brand_cost_6, brand_cost_1 * tmp_1)

    print(res)

📌 소감

조건을 잘 생각하면 되는 문제다.

[백준] 1049 - 기타줄

🖥 시작하며

⚙️ 코드

📌 소감

댓글