[그리디 알고리즘] 1049번 기타줄 풀이(파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- 백준 문제 링크입니다. : https://www.acmicpc.net/problem/1049

1049번: 기타줄

아래 작성된 답안은 제가 직접 작성 후 백준 페이지에서 채점하여 정답으로 인정된 답안입니다.
공식 답안이 아니므로 최적의 해가 아닐 수 있으며, 답안은 다른 분들과 상이할 수 있습니다.

[풀이]

n,m = list(map(int,input().split()))
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
package = []
solo = []
for i in a:
    package.append(i[0])
    solo.append(i[1])
final = [
    ((n//6)+1)*min(package),(n//6)*min(package)+(n%6)*min(solo),n*min(solo)
]
print(min(final))

분류를 3가지로 먼저 나누었습니다.

1. 패키지가 줄 1개 사는 것보다 싼 경우(패키지 가격 < 줄 1개 가격)

- (n//6+1) 개만큼 전부 가장 싼 package로 구매.

- 현실성은 없지만(이런걸 따질 문제가 아니므로) 줄 1개 가격은 무쓸모.

2. 패키지로 살 때 할인해주는 경우(줄 1개 가격 < 패키지 가격 < 줄 6개 가격)

- 몫(n//6) 개수만큼 가장 싼 package로 구매 + 나머지 (n%6) 개수만큼 줄 1개 가격으로 구매.

3. 전부 줄 1개 가격으로 구매(줄 6개 가격 < 패키지 가격)

- 이런 경우 패키지가 무쓸모.

 

1~3번을 각각 final이라는 리스트에 넣고, 그 중 최소 값을 출력하는 것으로 마무리했습니다.

 

중요한 것은, 최소한의 가지수로 발생할 수 있는 상황을 묶을 수 있는 능력인 것 같습니다.

 

감사합니다.