백준 3343번: 장미 (JAVA)

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

3343번: 장미

문제

상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다.

첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격이 저렴하면, N개 보다 많이 구매한 다음 남은 장미는 꽃집 점원에게 줄 것이다.

상근이가 장미를 적어도 N개 구매하는데 필요한 최소 금액을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, A, B, C, D가 주어진다. N은 1015를 넘지 않으며, A, B, C, D는 105를 넘지 않는다.

출력

첫째 줄에 장미를 적어도 N개 사는데 필요한 돈의 최솟값을 출력한다. 정답은 항상 1018을 넘지 않는다.

 

---

 

풀이

1. 아이디어

두 장미 세트의 가성비를 구한 후, '가성비가 안 좋은 장미 세트'는 A개(즉, 장미 AC개) 미만으로 구매하는 경우에서 최소 금액을 찾으면 된다. 아~~ 아이디어는 생각해냈는데, 구현에서 틀렸다.

2. 구현

나는 가성비가 좋은 세트로 다 사고 이후 하나씩 빼는 풀이를 생각했는데, 그냥 '가성비가 안 좋은 장미 세트'를 0개부터 A-1개 구매하는 경우를 for문 돌면 되더라.

구현은 (https://welog.tistory.com/436)를 참고하였다.

 

 

배운 점

구현을 잘 하자 - 초기 설계를 확실히 하지 않아, 코드 늪에서 헤엄치다가 발생한 실수

 

코드

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

public class Main {

	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 numA = Long.parseLong(st.nextToken());
		long priceA = Long.parseLong(st.nextToken());
		long numB = Long.parseLong(st.nextToken());
		long priceB = Long.parseLong(st.nextToken());
		
		if (priceA * numB < priceB * numA) {
			long priceTemp = priceA;
			priceA = priceB;
			priceB = priceTemp;
			long numTemp = numA;
			numA = numB;
			numB = numTemp;
		}
		
		long ans = Long.MAX_VALUE;
		
		for (int a = 0; a < numB; a++) {
			long b = (long) Math.ceil((double)(N - a*numA)/numB);
			boolean isOver = false;
			if (b < 0) {
				b = 0;
				isOver = true;
			}
			ans = Math.min(ans, a*priceA + b*priceB);
			if (isOver) break;
		}
		System.out.println(ans);
	}

}