[백준 1049] 기타줄

 

 

기타줄 6개 짜리 우선 구입 > 6개 짜리의 개수를 줄임 > 낱개 구입 순으로 각 케이스마다 돈의 최솟값을 그리디하게 찾아야 한다.

 

예를 들면,

n = 13, m = 1

6개 패키지 = 100 낱개 = 10

일때,

 

패키지 2개 + 낱개 1개 = 210

패키지 1개 + 낱개 7개 = 170

패키지 0개 + 낱개 13개 = 130

 

순으로 진행하며 매번 최솟값을 갱신한다.

 

구입할 수 있는 브랜드가 여러개일때는 6개 패키지와 낱개 를 각각 다른 브랜드에서 구입할 수 있으므로

완전탐색으로 해결했다.

 

 

public class Main {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int brand[][] = new int[m][2];
        
        int min = 100000000;
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            brand[i][0] = Integer.parseInt(st.nextToken());
            brand[i][1] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=0; i<m; i++) {
            for(int j=i; j<m; j++) {
                int pkg = 6;
                while(pkg <= n) {
                    pkg += 6;
                }
                min = min(min, pkg / 6 * brand[i][0]);
                
                pkg -= 6;
                while(pkg > -1) {
                    int k = 0;
                    while(k + pkg < n) {
                        k++;
                    }
                    min = min(min, (pkg / 6 * brand[i][0]) + (k * brand[j][1]));
                    pkg -= 6;
                }
            }
        }
        
        bw.write(min + "\n");
        bw.flush();
    }
    
    public static int min(int a, int b) {
        return a > b ? b : a;
    }
}