백준 1049번: 기타줄 C++코드(그리디 알고리즘, Greedy)

#include<iostream>

using namespace std;

int main(){
    int n,m;
    int packageArray[51];
    int singleArray[51];
    int result = 0;
    cin >> n >> m;
    int packageMin = 100000000;
    int singleMin = 100000000;
    for(int i=0; i<m; i++){
        cin >> packageArray[i] >> singleArray[i];
        if(packageArray[i] < packageMin){
            packageMin = packageArray[i];
        }
        if(singleArray[i] < singleMin){
            singleMin = singleArray[i];
        }
    }
    
    while(1){
        if(n <= 0){
            break;
        }
        if(n >= 6){
            if(packageMin < singleMin*6){
                result += packageMin;
                n -= 6;
            }else{
                result += singleMin*6;
                n -= 6;
            }
        }else{
            if(packageMin < singleMin*n){
                result += packageMin;
                n = 0;
            }else{
                result += singleMin*n;
                n = 0;
            }
        }
    }
    cout << result;

    
}

 

코드 줄이 길고 뭔가 더러워보이지만 전형적인 그리디 알고리즘을 사용한 코드이다. 

쉬운 그리디 알고리즘답게 약간의 구현 문제의 느낌이 난다. 남은 개수가 6개 이상인지 아닌지 따지고 6개 이상이면 낱개 6개 와 패키지를 비교. 남은 개수가 6개 미만이면 낱개 남은 개수 만큼과 패키지를 비교. 이정도가 핵심이다.