[백준oj] 1049번 기타줄

www.acmicpc.net/problem/1049

1049번: 기타줄

---

 

풀이)

1. 입력받은 패키지와 단품중, 최소값만 구한다.

2. {패키지,단품} 의 개수를 {0,N-6},{1,N-12},{2,N-18} , ... , {(N/6)+1,N-6*((N/6)+1)} 의 순서쌍을 탐색하며, 각 경우중 최소비용을 구하면된다.

3. (N/6)+1은 패키지를 사고, 단품이 남았을떄 패키지 가격 > 싱글*남은 단품개수 일 수 있으므로 고려해줬고, 단품의 개수는 앞의 경우와 같으면 음수가 나오므로 N-6*i와 0을 비교해서 N-6*i이 음수가 되면 0을 대입해주면 된다.

 

시간복잡도)

n/6+1 만큼 탐색하므로 O(N)이 된다.

 

코드)

#include<iostream>
#include<algorithm>
using namespace std;

int pack=9999,single=99999;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<m;i++){
        int p,s;
        cin>>p>>s;
        pack=min(pack,p);
        single=min(single,s);
    }
        
    int result=987654321;
    
    for(int i=0;i<=(n/6)+1;i++){
        result=min(result,pack*i+single*max(n-6*i,0));
    }
    
    cout<<result<<"\n";
    
	return 0;
}