백준 1049번(기타줄) 파이썬

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

1049번: 기타줄

이 문제는 보자마자 그리디 문제라고 파악을 했고 수학적인 연산도 필요할것이라 생각했다.

그리디 문제는 가장 효율적인 방법을 찾아내야 한다. 그래서 푸는데 시간이 좀 걸린 문제였다.

import sys
n,m= map(int,sys.stdin.readline().split())

arr1 = []
arr2 = []

for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    arr1.append(a)
    arr2.append(b)
min1=min(arr1)
min2=min(arr2)

if min1<min2*6: // 패키지가 더 싼경우
    if min1<(n%6)*min2: // 패키지의 갯수(6개)를 제외하고 남은 줄의 값의 낱개 합이 일반 패키지보다 비싼경우
        print((n//6)*min1+min1)
    else:
        print((n//6)*min1+(n%6)*min2)
elif min1>=min2*6: // 낱개가 더 싼경우
    print(n*min2)

수학이 굉장히 필요한 문제였다. 오랜만에 머리를 좀 쓴 느낌이라 뿌듯했다.

for 문안에서 각각 패키지 리스트와 낱개 리스트를 만들어 가장 싼 패키지, 낱개를 구한다.

그리고 첫번째 조건문에서는 패키지가 싼 경우와 낱개가 더 싼 경우로 나눈 다음

위의 주석을 참고하여 풀면 된다.

이번 문제는 경우의수를 따지는게 까다로웠다. 하지만

I did it.