[BOJ 3343 장미] 정수론, LCM

문제
최소공배수 구하는 방법

 

• $N =10^15$ 크다. 완탐하면 시간 초과 발생.
• 접근의 핵심은 두 수 a,b의 최소공배수 개념

 

접근법

최소공배수를 찾을 필요는 없지만 최소 공배수 개념을 활용해서 묶음의 가성비를 구한다.

 

A :  2 개 →    3원      X 10

B : 10개 →  14원      X  2

 

A :  20개 →   30원

B :  20개 →   28원  win

 

묶음의 가성비는 B가 더 좋다.

A의 묶음 개수 x, B의 묶음 개수 y라 할때

만약, 총 x*y(최소공배수) 개를 사야한다면 B를 x개 사는 것이 더 이득이다.

B를 x개 사는 게 더 이득이다. ==> A를 y개 이상 살 필요가 없다. (y-1개 이하일 땐 아니란 의미)

 

그러니 B에 묶음 가성비 좋은 가게로 설정해두고

A를 y개 미만일 때까지 가격을 비교하면 된다.

 

코드

#include <iostream>
#include <climits>
#include <cmath>

using namespace std;
typedef long long ll;

ll N, ans = LONG_MAX;
ll na, nb, ca, cb; // 묶음개수 ,가격 

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> na >> ca >> nb >> cb;

	//묶음 가성비 B가 더 좋게 설정 
	if (ca * nb < cb * na) {
		ll tmp = na; 
		na = nb; 
		nb = tmp;

		tmp = ca; 
		ca = cb; 
		cb = tmp;
	}

	//정확하게 따지면 cb가 아니라 최소공배수 만드는 배수겠지만
	// nb로 해도 답은 나오니까 
	// x : a의 묶음 개수
	// y: b의 묶음 개수 
	for (ll x = 0; x < nb; x++) {
		ll y = (long long)ceil((double)(N - na * x) / (double)nb);
		
		bool over = false;
		if (y < 0) {
			y = 0;
			over = true;
		}
		ans = min(ans, ca * x + cb * y);
		if (over) break;
	}
	cout << ans <<"\n";
		
	return 0;
}

 

 

 

참고

https://welog.tistory.com/436

https://velog.io/@alswndit/%EB%B0%B1%EC%A4%80-3343%EB%B2%88-%EC%9E%A5%EB%AF%B8-G4