이 글에서는 5개의 정수 변수 Num, P1, P2, profit_P1, profit_P2가 주어졌을 때, [1, Num] 범위에 있는 자연수들로부터 얻을 수 있는 총 이익을 극대화하는 방법을 다룹니다. 핵심 아이디어는 다음과 같습니다. 범위 내의 어떤 수가 P1으로 나누어 떨어지면 이익이 profit_P1만큼 증가하고, P2로 나누어 떨어지면 이익이 profit_P2만큼 증가합니다. 단, 하나의 수로부터 얻는 이익은 최대 한 번만 더할 수 있습니다.
예시로 이해하기
입력 − int num = 4, P1 = 6, P2 = 2, profit_P1 = 8, profit_P2 = 2;
출력 − 모든 사람 X의 총 이익 최댓값: 4
설명 − 여기서 숫자의 범위는 1부터 4까지입니다([1, Num(4)]).
이 범위에는 P1(6)으로 나누어 떨어지는 수가 없습니다.
2만이 P2(2)로 나누어 떨어지므로, 얻을 수 있는 이익은 2 × 2 = 4입니다.
입력 − num = 3, P1 = 1, P2 = 2, profit_P1 = 3, profit_P2 = 4;
출력 − 모든 사람 X의 총 이익 최댓값: 10
설명 − 1, 2, 3은 모두 A(P1 = 1)로 나누어 떨어집니다.
주어진 범위에서 B(P2 = 2)로 나누어 떨어지는 수는 2뿐입니다.
즉, 2는 A와 B 모두로 나누어 떨어지는 수입니다.
1과 3을 A로 나누면 이익은 2 × 3 = 6입니다.
2를 B로 나누면 이익은 1 × 4 = 4입니다.
2는 A와 B 모두로 나누어 떨어지지만, 이익을 극대화하려면 A 대신 B로 나누는 것이 유리합니다.
프로그램에 사용된 접근 방식
총 5개의 정수 변수가 주어집니다. 양수의 범위를 나타내는 Num, 첫 번째 사람을 의미하는 P1, 두 번째 사람을 의미하는 P2, 그리고 각각의 이익에 해당하는 profit_P1(범위 내의 수가 P1으로 나누어 떨어질 때 증가하는 이익)과 profit_P2입니다.
main 함수 안에서 모든 계산을 수행하는 유틸리티 메서드인 profitMaximisation()이 호출됩니다.
함수 내부를 보면, P1과 P2 모두로 나누어 떨어지는 수는 반드시 P1과 P2의 최소공배수(LCM)의 배수라는 사실을 알 수 있습니다. 따라서 이러한 수는 더 많은 이익을 주는 쪽으로 나누어야 합니다.
결국 최종 이익은 profit_P1 × (num / P1) + profit_P2 × (num / P2) − min(profit_P1, profit_P2) × (num / lcm(P1, P2)) 공식으로 계산됩니다.
주어진 두 수의 최소공배수를 구하기 위해 CalculateGcd() 메서드를 활용합니다. 최소공배수는 (P1 × P2) / GCD(P1, P2) 공식으로 구할 수 있습니다.
최종 결과값은 main 메서드에서 받아 사용자에게 출력됩니다.
예제 코드
public class testClass{
static int CalculateGcd(int n1, int n2){
if (n2 == 0)
return n1;
return CalculateGcd(n2, n1 % n2);
}
static int profitMaximisation(int n, int a, int b, int x, int y){
int result = x * (n / a);
result += y * (n / b);
result -= Math.min(x, y) * (n / ((a * b) / CalculateGcd(a, b)));
return result;
}
public static void main(String[] args){
int num = 6, P1 = 6, P2 = 2, profit_P1 = 8, profit_P2 = 2;
System.out.println("Maximize the total profit of all the persons X "+profitMaximisation(num, P1, P2, profit_P1, profit_P2));
}
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Maximize the total profit of all the persons X 12