[백준]1049-그리디(기타줄)

문제풀이

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

1. 인풋을 받는다. m개의 브랜드별로 세트의 가격과 낱개로 6개을 샀을 때의 가격을 비교해야 하기 때문에 이중리스트로 받게 한다

import math
n, m = map(int, input().split())
price = []
for i in range(m):
    price.append(list(map(int, input().split())))

2. 위에서 설명한 것처럼 브랜드별로 세트의 가격과 낱개로 6개 샀을 때의 가격을 비교해야 하기 때문에 세트 가격의 최솟값과 낱개 가격의 최솟값을 구해야 한다

#세트 가격의 최솟값
rope_set = []
    
for i in range(m):
    rope_set.append(price[i][0])
        
rope_set_price = min(rope_set)

#낱개 가격의 최솟값
rope_one = []
    
for i in range(m):
    rope_one.append(price[i][1])
        
rope_one_price = min(rope_one)

3. 먼저 기타줄의 개수(N)이 6보다 작은지 큰지를 나눠야 한다.

• n<6이라면 6개 세트의 가격과 낱개로 n개의 가격을 비교해서 최솟값을 구한다.
• n>=6이라면(n=6인경우는 어떤 경우의 수에 포함되든 상관이 없다) 2가지의 경우의 수를 또 생각해야한다.
• 다시 예를들어 34개의 기타줄을 구매해야 할 때 마지막 4개를 살 때 세트로 살지 낱개로 4개 살지 비교를 해야한다.

if n <= 6:
    print(min(rope_set_price, rope_one_price*n))
else:
    if (rope_one_price*6) < rope_set_price:
        print(rope_one_price*n)
    else:
        if rope_set_price < (rope_one_price*(n%6)):
            print(rope_set_price*(n//6+1))
        else:
            print(rope_set_price*(n//6) + rope_one_price*(n%6))

마무리

천천히 예시를 들어가면서 단계별로 알고리즘을 풀어나간다면 어렵지 않은 문제였다. 2874번 문제를 풀다가 머리가 너무 아파서 이 문제를 풀었는데 열심히 공부해서 그 문제도 풀 수 있도록 해야겠다.