[BOJ_3343] 장미

설명

---

가성비가 안 좋은 것을 모두 select하고 이때, 가성비가 좋은 것을 후 순위로 선택하면서 Math.min 값을 줄여나가는 풀이로 풀어야 한다.

 

그리디 형태로 어떻게 풀까 싶었는데 도저히 떠오르지 않아서 풀이를 보고 해결했다. 조금 생각하기가 버거웠던 문제

 

 

코드

---

package Math;

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

public class BOJ_3343 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

        if (B * C < D * A) { // D/C > B/A ->  D / C * A > B -> D * A > B * C (가성비가 안 좋은 것을 선택)
            long priceTemp = B;
            B = D;
            D = priceTemp;
            long numTemp = A;
            A = C;
            C = numTemp;
        }

        long ans = Long.MAX_VALUE;

        for (int a = 0; a < C; a++) { //가성비가 안 좋은 것을 돌림 두번째 것을 안 좋은 가성비로 판단
            long b = (long) Math.ceil((double)(N - a * A)/C);
            //올림 처리 즉, 조금이라도 남으면 가성비 좋은 것 대신 갯수가 많을 수도 있는것을 산다.
            if (b < 0) {
                break;
            }
            ans = Math.min(ans, a * B + b * D);

        }
        System.out.println(ans);
    }
}

 

3343번: 장미