문제
https://www.acmicpc.net/problem/3343
풀이 방법
첫 번째 꽃집에서는 장미 A개를 B원에 팔고, 두 번째 꽃집에서는 장미 C개를 D원에 팔 때 2개의 꽃집에서 N개의 장미를 사기위한 최소 금액을 구하는 문제이다. 묶음으로 판매하기 때문에 N개이상의 장미를 사도 상관없다.
사려고하는 장미의 최대 개수는 1e15 - 1 개이므로 개수를 기준으로 모든 경우를 탐색한다면 시간초과가 발생한다. 그러므로 탐색을 멈춰도 되는 적절한 조건을 찾아야 한다.
첫 번째 가게에서는 3개를 15원에 팔아 1개당 가격은 5원이고, 두 번째 가게에서는 4개를 19원에 팔아 1개당 가격은 4.75원이다. 1개당 가격으로 보면 두 번째 가게에서 사는 것이 가성비가 좋다. 하지만 해당 문제는 개수가 아닌 묶음으로 사야한다.
1 ~ 3 송이를 살 때는 첫 번째 가게에서 사야 최소 금액으로 구매할 수 있다. 4 송이를 살 때는 첫 번째 가게에서 2묶음을 사야 하기 때문에 두 번째 가게에서 사는 것이 좋다. 즉, 묶음 단위로 사기 때문에 1개당 가격에 초점을 두면 안된다.
3과 4의 최소공배수(LCM)인 12개를 사려고 한다. 첫 번째 가게에서만 사면 3개짜리 4묶음을 사야 하기 때문에 60원이고, 두 번째 가게에서만 사면 4개짜리 3묶음을 사야 하기 때문에 57원이다. 장미 3개를 4번 사는 것보다 장미 4개를 3번 구매하는 것이 더 저렴하기 때문에 장미 3개를 4번 이상 살 필요가 없다.
즉, 두 가게에서 팔고자하는 단위의 최소공배수 만큼의 장미를 살 때 더 저렴한 곳을 찾으면 된다. A개를 B번 사는 것보다 B개를 A번 사는 것이 더 저렴하다면 A개를 B번이상 살 필요가 없음에 초점을 두어야 한다.
3과 4의 최소공배수인 12개를 살 때는 두 번째 가게에서 사는 것이 더 가성비 좋다. 그렇기 때문에 사려고하는 장미의 개수가 31개이면 12 X 2 = 24 개를 두 번째 가게에서 먼저 산다음 나머지 7개를 brute force 로 탐색해도 될 것 같은 느낌도 든다. 하지만 가성비가 좋은 가게에서 처리할 수 있는 최대 개수를 먼저 구매하면 최소 금액을 절대 구할 수 없다.
가성비가 좋은 가게에서 먼저 구매할 경우 13개를 구매하기 위해 가성비가 좋은 두 번째 가게에서 12개인 3묶음을 먼저사고 나머지 1개를 첫 번째 가게에서 1묶음을 사면 72원이다.
하지만 13개를 첫 번째 가게에서 9개인 3묶음을 사고 두 번째 가게에서 4개인 1묶음을 사면 64원으로 더 저렴하게 구매할 수 있다.
두 가게에서 팔고자하는 단위의 최소공배수 만큼의 장미를 구매해 더 저렴한 경우를 찾은 이유는 가성비 좋음을 찾기 위함이 아니고 A개를 B번 사는 것보다 B개를 A번 사는 것이 더 저렴하다면 A개를 B번이상 살 필요가 없음을 구하기 위해서 였다.
코드
package day0214;
import java.io.*;
import java.util.*;
public class BOJ_G4_3343_장미 {
static long N, min = Long.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Long.parseLong(st.nextToken()); // 장미 개수
long cntA = Long.parseLong(st.nextToken()); // 꽃집A의 꽃다발 장미 개수
long priceA = Long.parseLong(st.nextToken()); // 꽃집A의 꽃다발 가격
long cntB = Long.parseLong(st.nextToken()); // 꽃집B의 꽃다발 장미 개수
long priceB = Long.parseLong(st.nextToken()); // 꽃집B의 꽃다발 가격
// A : 가성비 좋은 세트, B : 가성비 안좋은 세트로 저장 => A를 B개 구매한 가격 < B를 A개 구매한 가격
if(cntB*priceA > cntA*priceB) {
long cntTmp = cntA;
cntA = cntB;
cntB = cntTmp;
long priceTmp = priceA;
priceA = priceB;
priceB = priceTmp;
}
for(int b=0; b<cntA; b++) { // B를 A개 이상 구매할 필요가 없다
long a = (long) Math.ceil((double)(N - b*cntB)/cntA);
boolean isOver = false;
if (a < 0) {
a = 0;
isOver = true;
}
min = Math.min(min, a*priceA + b*priceB);
if(isOver) break;
}
System.out.println(min);
}
}