장미

풀이

 N개의 장미를 가장 싸게 구매할 수 있는 금액을 구하는 문제이다. 입력값의 범위가 크므로 DP나 완전탐색 등은 불가능하다. 문제 해결 아이디어는 아래와 같다.

1. 가성비가 좋은 장미(X)와 가성비가 좋지 못한 장미(Y)로 나눈다.
2. Y는 X개 보다 적은 경우에만 정답이 나올 수 있으므로 Y를 0개부터 X-1개 까지 구매하는 경우의 수를 전부 확인하여 결과값을 찾아낸다.

시간 복잡도 : O(c)(c: 특정 상수)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long n = Long.parseLong(st.nextToken());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        long d = Long.parseLong(st.nextToken());
        long result = Long.MAX_VALUE;

        if (b * c < d * a) {
            long temp;
            temp = a;
            a = c;
            c = temp;
            temp = b;
            b = d;
            d = temp;
        }

        for (int i = 0; i < c; ++i) {
            long index = (long) Math.ceil((double) (n - i * a) / c);

            if (index < 0) {
                index = 0;
            }
            result = Math.min(result, i * b + index * d);

            if (index == 0) {
                break;
            }
        }

        bw.write(result + "\n");
        bw.close();
    }
}