목록3343 (1)

hyunjin

[BOJ 3343 장미] 정수론, LCM

문제최소공배수 구하는 방법 $N =10^15$ 크다. 완탐하면 시간 초과 발생.접근의 핵심은 두 수 a,b의 최소공배수 개념 접근법최소공배수를 찾을 필요는 없지만 최소 공배수 개념을 활용해서 묶음의 가성비를 구한다. A :  2 개 →    3원      X 10B : 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개 미만일 때까..
알고리즘 연습/백준 2024. 4. 25. 17:17
이전 Prev 1 Next 다음