다섯 개의 정수 N, A, B, X, Y가 주어졌을 때, 1부터 N까지의 범위에 있는 숫자들을 검사하여 이익을 최대화하는 것이 목표입니다.
- 숫자가 A로 나누어 떨어지면 이익이 X만큼 증가합니다.
- 숫자가 B로 나누어 떨어지면 이익이 Y만큼 증가합니다.
단, 범위 내의 각 숫자에 대해서는 이익이 한 번만 추가될 수 있습니다. 만약 어떤 숫자가 A와 B 모두로 나누어 떨어진다면, X와 Y 중 더 큰 값을 선택하는 것이 유리합니다.
예제로 이해하기
예제 1
입력: N=4, A=2, B=3, X=2, Y=3
출력: 최대 이익 = 7
설명:
- 2와 4는 A(2)로 나누어 떨어집니다. 이익이 0 → 2 → 4로 증가합니다 (X=2씩).
- 3은 B(3)로 나누어 떨어집니다. 이익이 4 → 7로 증가합니다 (Y=3).
예제 2
입력: N=5, A=2, B=4, X=1, Y=3
출력: 최대 이익 = 4
설명:
- 2와 4는 A(2)로 나누어 떨어집니다.
- 4는 B(4)로도 나누어 떨어집니다.
- 2의 경우 이익이 0 → 1로 증가합니다 (X 적용).
- 4의 경우 B로 나누어 떨어지므로 Y를 선택합니다. Y가 X보다 크기 때문입니다. 따라서 이익이 1 → 4로 증가합니다 (Y=3).
알고리즘 접근 방식
- 정수 N, A, B, X, Y를 입력받습니다.
maximizeProfit(int n, int a, int b, int x, int y)함수가 이익을 계산하여 반환합니다.- 변수
profit은 총 이익을 저장하며, 초기값은 0입니다. - for 반복문으로 1부터 n까지 각 숫자 i가 a와 b로 나누어 떨어지는지 확인합니다.
- i가 a와 b 모두로 나누어 떨어지면 x와 y 중 더 큰 값을 이익에 더합니다.
- i가 a로만 나누어 떨어지면 x를 더합니다.
- i가 b로만 나누어 떨어지면 y를 더합니다.
- 마지막으로 profit에 저장된 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 최대 이익을 반환하는 함수
int maximizeProfit(int n, int a, int b, int x, int y){
int profit=0;
for(int i=1;i<=n;i++){
if(i%a==0 && i%b==0){
int maxx=x>=y?x:y;
profit+=maxx;
}
else if(i%a==0){
profit+=x;
}
else if(i%b==0){
profit+=y;
}
}
return profit;
}
int main(){
int N = 6, A = 2, B =4, X = 6, Y = 3;
cout <<"Maximized profit is: "<<maximizeProfit(N,A,B,X,Y);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Maximized profit is: 2
이 알고리즘의 시간 복잡도는 O(N)으로, 1부터 N까지 한 번씩만 순회하면 되기 때문에 효율적입니다. 만약 N이 매우 큰 값이라면, 배수의 성질을 이용해 A의 배수 개수 × X + B의 배수 개수 × Y − 최소공배수(LCM)의 배수 개수 × min(X, Y) 공식으로 O(1) 시간에 계산할 수도 있습니다.