문제 개요
서로 다른 크기를 가진 두 종류의 물건, 즉 큰 장난감과 작은 장난감이 있다고 가정해 봅시다. 물건의 종류는 사용자가 자유롭게 정할 수 있으며, 여기서는 이해를 돕기 위해 크기 속성에 따라 구분되는 장난감을 예로 들겠습니다.
이 문제의 목표는 작은 장난감을 교환해서 얻을 수 있는 큰 장난감의 최대 개수를 계산하는 것입니다. 교환 규칙은 다음과 같습니다.
- a : 큰 장난감 1개를 얻기 위해 필요한 작은 장난감의 개수
- b : 큰 장난감 1개를 포기했을 때 돌려받는 작은 장난감의 개수
만약 b가 a보다 크다면(b > a), 큰 장난감을 작은 장난감으로 바꿨다가 다시 큰 장난감으로 되돌리는 과정에서 이득이 발생합니다. 따라서 이 경우에는 먼저 보유한 모든 큰 장난감을 작은 장난감으로 바꾸는 것이 유리합니다.
입출력 예시
입력 : big_toys = 8, small_toys = 20, a = 6, b = 4
출력 : 교환을 통해 얻을 수 있는 큰 장난감의 최대 개수는 11개
설명 : 보유한 작은 장난감 20개를 교환하면 큰 장난감 3개(20 ÷ 6 = 3)를 추가로 얻을 수 있습니다. 기존의 8개와 합치면 총 11개가 됩니다.
입력 : big_toys = 3, small_toys = 10, a = 4, b = 2
출력 : 교환을 통해 얻을 수 있는 큰 장난감의 최대 개수는 5개
설명 : 작은 장난감 10개로는 큰 장난감 2개(10 ÷ 4 = 2)를 얻을 수 있습니다. 기존의 3개와 합치면 총 5개입니다.
풀이 접근 방법
- 큰 장난감과 작은 장난감의 총 개수를 입력받습니다. 동시에 'a'(큰 장난감 1개를 얻는 데 필요한 작은 장난감 수)와 'b'(큰 장난감 1개를 내놓을 때 받는 작은 장난감 수)도 함께 입력받습니다.
- a < b인 경우, 큰 장난감을 작은 장난감으로 교환하는 것이 이득입니다. 이때는 보유한 모든 큰 장난감을 작은 장난감으로 바꿔 누적하고(big_toys × b만큼 증가), 큰 장난감 개수는 0으로 초기화합니다.
- 이후 전체 작은 장난감 개수를 a로 나눈 몫만큼 큰 장난감을 추가로 확보합니다.
- 계산된 큰 장난감의 총 개수를 반환합니다. 이 값이 작은 장난감과 교환하여 얻을 수 있는 큰 장난감의 최대 개수입니다.
- 최종 결과를 출력합니다.
C++ 예제 코드
#include <iostream>
using namespace std;
int maximum(int big_toys, int small_toys, int a, int b){
if (a < b){
small_toys += b * big_toys;
big_toys = 0;
}
big_toys += (small_toys / a);
return big_toys;
}
int main(){
int big_toys = 8, small_toys = 20;
int a = 6, b = 4;
cout << "Maximize big when both big and small can be exchanged are:" << maximum(big_toys, small_toys, a, b);
return 0;
}
실행 결과
Maximize big when both big and small can be exchanged are: 11
복잡도 분석
이 풀이는 단순한 산술 연산만으로 답을 구하므로 시간 복잡도는 O(1)입니다. 또한 입력값 외에 별도의 저장 공간을 사용하지 않으므로 공간 복잡도 역시 O(1)로, 어떤 입력 규모에서도 일정한 성능을 보장합니다.