[BOJ] 백준 3343 장미

[문제]

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

 

 

[소스 코드]

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));
		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(a*d > b*c) {
			long tmpCnt = a;
			a = c;
			c = tmpCnt;
			long tmpCost = b;
			b = d;
			d = tmpCost;
		}
		long lcm = LCM(a,c);
		long min = Long.MAX_VALUE;
		for(long i=0;i<lcm/a;i++) {
			long cost = i*b;
			if(n-i*a>0) 
				cost += Math.ceil((double)(n-i*a)/c) * d;
			min = Math.min(min, cost);
		}
		System.out.println(min);
	}
	private static long LCM(long a,long c) {
		long cpA = a;
		long cpC = c;
		while(cpA!=0) {
			long tmpA = cpA;
			cpA = cpC%cpA;
			cpC = tmpA;
		}
		return a / cpC * c;
	}
}