[BOJ 1049] 기타줄

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

1049번: 기타줄

"끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오."

 

 

 

가장 최소의 금액으로, 끊어진 기타줄을 고칠 수 있는 방법을 찾아야 한다.

 

 

 

그러기 위해서 필요한 것은, 가장 싼 패키지 가격, 가장 싼 낱개 가격을 이용해야 한다. 이 부분에서 그리디 알고리즘의 정의가 들어갔다.

 

 

 

만약, 낱개를 6개 사는 것이 패키지보다 싸다면, 패키지를 살 필요가 없다. 현실에선 패키지가 당연히 싸겠지만, 알고리즘 문제에서는 그렇지 않다.

 

 

 

만약, 낱개가 더 싸다면, 낱개로만 구매하면 된다.

 

 

 

하지만, 패키지가 더 싸다면 패키지와 낱개를 조합해야 한다. 조합해야 하는 경우에도 문제가 발생한다.

 

 

 

패키지로 최대한 구매하고, 남은 낱개들을 패키지로 구매할 것인지 아니면 낱개로 구매할 것인지 확인을 해야 한다.

 

 

 

위의 코드를 구현하면 아래와 같다.

 

 

 

정답률에 비해서, 문제는 쉬웠다. 사람마다 차이가 있겠지만, 크게 어렵지 않을 것이다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N, M;
int m_set = 1001;
int m_one = 1001;
int val1, val2;
 
int main() {
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> val1 >> val2;
        m_set = min(m_set, val1);
        m_one = min(m_one, val2);
    }
    
    if(m_set < m_one * 6){
        cout << min(m_set * (N / 6) + (N % 6) * m_one, m_set * (N / 6 + 1)) << endl;
    }else
        cout << m_one * N << endl;
        
    return 0;
}