크기가 n인 두 개의 배열 A와 크기가 m인 배열 B, 또 다른 숫자 r이 있다고 가정합니다. 주식을 살 수 있는 기회는 n번 있습니다. 그 중 i번째는 우리가 원하는 만큼의 주식을 살 수 있도록 하며, i번째 주가는 A[i]입니다. 또한 주식을 팔 수 있는 기회가 m 있습니다. 그 중 i번째는 우리가 원하는 만큼의 주식을 판매할 수 있도록 하며, i번째 주식의 판매 가격은 B[i]입니다. 우리가 가진 것보다 더 많은 주식을 팔 수는 없습니다. 만약 우리에게 r개의 돈이 있고 기존 주식이 없다면 우리는 사고 팔고 난 후에 우리가 보유할 수 있는 최대 돈을 찾아야 합니다.
따라서 입력이 A =[4, 2, 5]와 같으면; B =[4, 4, 5, 4]; r =11이면 11개의 돈이 있으므로 출력은 26이 됩니다. 주식 5주를 2의 가격에 사서 5의 가격에 모두 파는 것이 최적입니다. 따라서 결국 26주를 얻을 수 있습니다.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
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 r
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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