백준 1049 기타줄

설명

• 최소 금액을 구하는 문제이다.
• 고민이 됐었지만, 6으로 나눠서 가장 많이 갯수를 채우고 + 나머지 1로 가장 많이 갯수를 채우면 되는 것으로 확인되었다.
• 6으로 나눈값과 + 나머지를 혼합하는 케이스만 처음에 제출했었는데 틀렸다.
• 6으로만 하는게 가장 싼 경우가 있기 때문이다. 그래서 해당 케이스를 추가해서 제출했는데 틀렸다.
• 1으로만 하는게 가장 싼 경우가 있기 때문이다. 

반례(1으로만 하는게 가장 싸다 2*12 = 24)

12 2
20 4
15 2
24

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    // 1049
    public static void main(String[] args) throws IOException {
        process();
    }

    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        final int N = Integer.parseInt(st.nextToken());
        final int M = Integer.parseInt(st.nextToken());

        final int sixCnt = N / 6;
        final int onCnt = N % 6;
        int minSixPrice = Integer.MAX_VALUE;
        int minOnePrice = Integer.MAX_VALUE;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            minSixPrice = Math.min(minSixPrice, Integer.parseInt(st.nextToken()));
            minOnePrice = Math.min(minOnePrice, Integer.parseInt(st.nextToken()));
        }

        final int mixPrice = minSixPrice * sixCnt + minOnePrice * onCnt;
        final int onlySixPrice = (sixCnt+1) * minSixPrice;
        final int onlyOnePrice = minOnePrice * N;

        bw.write(Math.min(onlyOnePrice, Math.min(mixPrice, onlySixPrice)) + "");
        bw.flush();
        bw.close();
        br.close();
    }
}