두 개의 사물함 L1과 L2가 있으며, 각각 동전 형태로 돈이 들어 있다고 가정해 보겠습니다. L1에는 A개의 동전이, L2에는 B개의 동전이 들어 있습니다. 우리는 이 사물함들에서 동전을 인출하되, 인출한 총 금액이 최대가 되도록 만들어야 합니다. 사물함에서 동전을 인출할 때마다 해당 사물함은 이전 개수보다 1개 적은 동전으로 다시 채워집니다. 즉, L1에서 A개의 동전을 인출하면 A-1개로 채워지고, L2에서 B개의 동전을 인출하면 B-1개로 채워집니다. 따라서 과제는 정확히 두 번의 인출 단계 동안 인출 금액을 최대화하는 것입니다.
예제 입력 및 출력
입력 − L1 - 10, L2 - 11
출력 − 두 번의 인출로 얻을 수 있는 최대 금액 - 21
설명 − 1단계에서 L2에서 11개의 동전을 인출하면, L2는 11-1=10개의 동전으로 다시 채워집니다.
2단계에서는 L1과 L2가 모두 10개의 동전을 가지고 있으므로 어느 쪽에서든 인출할 수 있으며, 총 11+10=21개로 최댓값이 됩니다.
입력 − L1 - 5, L2 - 5
출력 − 두 번의 인출로 얻을 수 있는 최대 금액 - 10
설명 − 1단계에서 L1에서 5개의 동전을 인출하면, L1은 5-1=4개의 동전으로 다시 채워집니다.
2단계에서는 L1에 4개, L2에 5개의 동전이 있으므로 L2에서 5개를 인출하여 총 5+5=10개로 최댓값이 됩니다.
프로그램에 사용된 접근 방식
동전이 일정량 들어 있는 두 개의 사물함 L1과 L2를 정수 값으로 표현합니다.
maxMoney(int A, int B) 함수는 각 사물함의 동전 개수를 입력으로 받습니다.
maxMoney() 함수 내부에서 최대 금액을 저장하기 위한 변수 'money'를 선언합니다.
처음에 money는 A와 B 중 더 큰 값으로 초기화됩니다. (money = A>B ? A : B)
money의 값을 A 또는 B와 비교하여 어느 사물함에서 동전을 인출했는지 판별합니다.
인출된 사물함의 동전 개수를 이전보다 1개 적게 줄입니다. (A-- 또는 B--)
다시 money에 A와 B 중 더 큰 값을 더합니다. (money += A>B ? A : B)
누적된 money 값을 최종 결과로 반환합니다.
이 방법이 최적인 이유
이 접근 방식이 항상 최적의 결과를 보장하는 이유는 간단합니다. 동전이 더 많은 사물함에서 몫 전체를 인출하더라도, 해당 사물함은 단 1개의 동전만 줄어든 상태로 다시 채워지기 때문입니다. 따라서 두 번의 인출에서 각각 가능한 한 많이 가져가는 그리디(greedy) 전략이 최선이며, 이 알고리즘은 O(1)의 상수 시간 복잡도로 해결됩니다.
예제 코드
#include <stdio.h>
#include <math.h>
// 얻을 수 있는 최대 동전 개수를 반환하는 함수
int maxMoney(int A, int B){
// 먼저 더 많은 쪽에서 동전을 인출
int money = A>B ? A : B;
// 인출된 사물함을 1개 적은 동전으로 다시 채움
if(money == A)
A--;
else
B--;
// 두 번째 인출 진행
money += A>B ? A : B;
return money;
}
// 드라이버 코드
int main(){
int L1 = 8, L2 = 9;
printf("Maximum money that can be withdrawn in two steps: %d", maxMoney(L1, L2));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Maximum money that can be withdrawn in two steps: 17