문제

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

Silver IV

코드 (Java)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        sc.nextLine();
        int min_six_cost = 2000, min_single_cost = 2000;

        for (int i = 0; i < M; ++i) {
            int six_cost = sc.nextInt(), single_cost = sc.nextInt();
            sc.nextLine();
            if (six_cost < min_six_cost) min_six_cost = six_cost;
            if (single_cost * 6 < min_six_cost) min_six_cost = single_cost * 6;
            if (single_cost < min_single_cost) min_single_cost = single_cost;
        }

        int min_cost = min_six_cost * (N / 6);
        if (min_single_cost * (N % 6) > min_six_cost) min_cost += min_six_cost;
        else min_cost += (min_single_cost * (N % 6));

        System.out.println(min_cost);
        sc.close();
    }
}

풀이

그리디 알고리즘

유의해야 하는게, 단일 줄을 여러개 사는것보다 여섯개의 줄을 사는 것이 더 이득인 경우가 있을 수 있다.

예를 들어 단일 줄 가격이 3이고 여섯개 줄 가격이 8이면, 3개 이상 사야할 때 부터는 여섯개 세트를 사는게 더 이득이다.

또한 여섯개 줄 가격이 단일 줄 여섯개 가격보다 더 큰 경우도 고려 해야 한다.