두 개의 배열 A(크기 n), B(크기 m)와 하나의 숫자 r이 주어졌다고 가정해 봅시다. 주식을 구매할 수 있는 기회가 총 n번 있으며, i번째 기회에서는 원하는 만큼 주식을 살 수 있고 그때의 가격은 A[i]입니다. 마찬가지로 주식을 판매할 수 있는 기회가 총 m번 있으며, i번째 기회에서의 판매 가격은 B[i]입니다. 단, 보유한 주식보다 많이 팔 수는 없습니다.
초기 자금 r이 있고 현재 보유한 주식이 없을 때, 매수와 매도를 모두 마친 후 가질 수 있는 최대 금액을 구하는 것이 이 문제의 목표입니다.
문제 예시
예를 들어 입력이 다음과 같다고 해봅시다.
- A = [4, 2, 5]
- B = [4, 4, 5, 4]
- r = 11
이 경우 출력은 26입니다. 그 이유는 다음과 같습니다. 처음 가진 11의 자금으로 가격이 2인 시점에서 주식을 최대한 많이, 즉 5주를 구매합니다(11 ÷ 2 = 5주, 나머지 1). 이후 가격이 5일 때 5주를 모두 판매하면 25를 얻게 되고, 여기에 남아 있던 나머지 1을 더해 최종적으로 26을 가지게 됩니다.
풀이 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열 A에서 가장 낮은 매수 가격(an)을 찾습니다.
- 배열 B에서 가장 높은 매도 가격(bn)을 찾습니다.
- 만약 최고 매도 가격이 최저 매수 가격보다 크다면(bn > an), 가능한 한 많은 주식을 싸게 사서 비싸게 파는 것이 이득입니다. 이때 남는 잔돈은 그대로 보관합니다.
- 그렇지 않다면(bn ≤ an), 거래를 하지 않는 것이 최선이므로 원래 자금 r을 그대로 반환합니다.
의사 코드
n := size of A
an := 1100
bn := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
if an > A[i], then:
an := A[i]
for initialize i := 0, when i < m, update (increase i by 1), do:
if bn < B[i], then:
bn := B[i]
if bn > an, then:
r := bn * (r / an) + (r - (r / an) * an)
return rC++ 구현 예제
위 로직을 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B, int r){
int n = A.size(), m = B.size();
int an = 1100, bn = 0;
for (int i = 0; i < n; i++){
if (an > A[i])
an = A[i];
}
for (int i = 0; i < m; i++){
if (bn < B[i])
bn = B[i];
}
if (bn > an){
r = (bn) * (r / an) + (r - (r / an) * an);
}
return r;
}
int main(){
vector<int> A = { 4, 2, 5 };
vector<int> B = { 4, 4, 5, 4 };
int r = 11;
cout << solve(A, B, r) << endl;
}입력
{ 4, 2, 5 }, { 4, 4, 5, 4 }, 11출력
26
정리
이 문제의 시간 복잡도는 배열을 한 번씩만 순회하므로 O(n + m)이며, 공간 복잡도는 O(1)로 매우 효율적입니다. 핵심은 '가장 싸게 살 수 있는 가격'과 '가장 비싸게 팔 수 있는 가격'만 확인하면 된다는 점입니다. 매도 가격이 매수 가격보다 높지 않다면 아예 거래하지 않는 것이 최대 자산을 지키는 방법이라는 점도 기억해 두세요.