백준 1049번 - 기타줄

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

처음에 문제를 제대로 이해하지 못해서 헤매다가 1시간의 삽질 끝에 문제를 해결했다..

막상 문제를 풀어보니 문제의 조건에 대한 설명이 조금 부족한 것 같아서 아쉬웠다.

먼저 문제에 제시된 N과 M값이 작다보니 O(N*M)으로도 문제를 풀 수 있었고 O(N+M)으로도 문제를 풀 수 있었다.

우선 M개의 브랜드가 있다고 나와있는데 나도 모르게 중복이 안된다고 가정하고 문제에 접근했다.

그러나 특정 브랜드를 계속해서 살 수 있기 때문에 따로 중복체크를 할 필요가 없다.

첫 번째로 문제를 해결한 방법은

N개를 6개씩 빼주면서 패키지로 사는 경우와 낱개를 6개 사는 경우를 M번 비교해서 가장 적은 비용을 더해주는 방식이다.

만약 N이 6개 이하라면 패키지로 사는 경우와 낱개를 N개 사는 경우를 M번 비교해주면 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    
    int N,M;
    cin>>N>>M;
    
    vector<vector<int>> vec(M,vector<int>(2,0));
    
    for(int i=0;i<M;i++)
        scanf("%d %d",&vec[i][0],&vec[i][1]);
    
    
    int ans=0,cnt=0;
    while(N){
        
        cnt=(N>=6)? 6:N;
        N-=cnt;
        
        int cost=1000;
        for(int i=0;i<M;i++)
            cost=min(cost,min(vec[i][0],vec[i][1]*cnt));
        
        ans+=cost;
    }
    
    cout<<ans<<endl;
    return 0;
}
 
 
 
 

두 번째로 문제를 해결한 방법은

미리 패키지와 낱개로 사는 경우 중에 가장 적은 비용이 드는 것을 구하는 것이다.

이때 3가지 경우로 나눌 수 있다.

1. N이 6개 이하일 때

2. N이 6개 이상이면서 6으로 나누어떨어질 때

3. N이 6개 이상이면서 6으로 나누어떨어지지 않을 때

위의 경우에 따라서 각각 패키지와 낱개를 계산하는 방법을 예외 처리 해주면 답을 구할 수 있게 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    
    int N,M;
    cin>>N>>M;
    
    vector<vector<int>> vec(M,vector<int>(2,0));
 
    int cost_package=1000;
    int cost_unit=1000;
    for(int i=0;i<M;i++){
        scanf("%d %d",&vec[i][0],&vec[i][1]);
        cost_package=min(cost_package,vec[i][0]);
        cost_unit=min(cost_unit,vec[i][1]);
    }
    
    int ans=0;
    if(N<6){
        ans=min(cost_package,cost_unit*N);
    }else{
        
        if(N%6==0){
            ans=min(cost_package*(N/6),cost_unit*N);
        }else{
            ans=min(cost_package*(N/6)+cost_unit*(N%6),cost_unit*N);
            ans=min(ans,cost_package*(N/6+1));
        }
    }
   
    cout<<ans<<endl;
    return 0;
}