BOJ 1049 기타줄

기타줄이 N개 필요한데, 기타줄을  6개씩 묶어서 팔거나 낱개로 팔기도 한다.
6개씩 묶어서 파는 가격과 낱개의 가격이 주어질 때, 기타줄을 적어도 N개 사기 위해 필요한 돈의 최소값을 구하는 문제이다.

N개만 사는 최소 비용을 구하는 문제라면 동전dp처럼 풀면 될 것 같은데... 음 이건 N개 이상을 사는 최소 비용을 구하는 문제라고 볼 수 있으니
d[N] = N개 이상의 기타줄을 구매하기 위해 필요한 최소 비용 ...
음... 문제 분류를 얼떨결에 봐버렸다.
그리디 알고리즘으로 돼있다... 아...

그렇다. 다시 생각해보니 굳이 dp를 쓸 필요가 없다...
지금 브랜드 별로 6개짜리 묶음 가격과 낱개 가격이 주어지는데, 6개 묶음 가격중에서, 낱개 가격중에서 각각 제일 싼 가격을 택하면 된다.
즉, 이 문제는 6개 묶음 가격과 낱개 가격이 하나씩만 주어지는 문제가 되는 것이다.

그리고 6개 묶음 가격이 낱개로 했을 때는 얼마인지 보고, 6개 이상의 기타줄에 대해서는 낱개로 사는 것이 나은지 6개묶음으로 사는 것이 나은지 판단해본다.

그리고 낱개로 사는 것이 더 낫다면 바로 답을 구할 수 있을 것이고,
그게 아니라면 좀 더 생각해 봐야한다.
6개묶음으로 사는 것이 더 쌀 경우 N이 6의 배수라면 답이 나올 것인데, 그렇지 않다면 좀 더 생각해 봐야한다.

N이 6의 배수가 아니라면
 (N/6+1) * (묶음 가격) 이 더 싼지, (N/6) * (묶음 가격) + (N%6) * (낱개 가격) 이 더 싼지 비교해봐서 답을 구하면 될 것이다.