SW Expert Academy 1859_백만장자 프로젝트 문제풀이 in C++
문제 URL
문제 요구사항
- 25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
- 다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
- 다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.
1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다. 2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다. 3. 판매는 얼마든지 할 수 있다.
[입력]
- 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.
- 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
- 각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
- 둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
- 각 날의 매매가는 10,000이하이다.
[출력]
- 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.
접근 방법
- 정방향 탐색을 할 것이냐, 역방향 탐색을 할 것이냐를 정한다.
- 정방향의 경우, max_index를 찾아 해당 인덱스 전까지 계속 구매 후, 해당 인덱스에서 모두 판매하는 것을 반복한다.
- 역방향의 경우
1. 가장 마지막 인덱스의 값을 max_price에 넣는다. 2. for문을 가장 마지막 인덱스부터 0 인덱스까지 돌도록 해 조건문을 활용하여 다음 조건 계산 max_price이 v ( 입력 받은 금액 벡터 ) [ i ]보다 크거나 같으면, result 값에 result + (max_price - v[ i ] ) 값을 넣는다. max_price보다 v[ i ]의 값이 크다면, max_price에는 v[ i ] 값을 넣는다.
- 나중에 입력 받은(다음 날)이 작다면 해당 날에는 팔지 않았을 것이고, 크다면 그 날에 팔았을 것이라는 것을 가정하고 계산하게 된다.
풀이 순서
- T를 입력 받아 해당 크기만큼 for문을 반복하여 test_case를 수행한다.
- N을 입력받고, 해당 N의 크기만큼 매매가를 입력받아 저장한다.
- 저장한 매매가 정보의 마지막 인덱스 값을 max_price에 저장한다.
- for문 수행 N-1부터 0까지
- max_price의 값이 v [ i ]보다 크거나 같다면 -> 해당 max_price 날에 판매한다는 것이 되므로, res = res + (max_price - v[ i ])
- 반대로 max_price 값이 v [ i ]보다 작다면 -> 해당 max_price 날을 갱신해줘야 하므로, max_price = v [ i ]
- 이와 같은 작업 반복
- 각 test_case 마다 계산한 res를 출력
소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> v;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
for (int test_case = 1; test_case <= TC; test_case++) {
long long N;
cin >> N;
v.clear();
for (long long i = 0; i < N; i++) {
int price;
cin >> price;
v.push_back(price);
}
int max_price = v[N - 1];
long long res = 0;
for (int i = N - 1; i >= 0; i--) {
if (max_price >= v[i]) {
res = res + (max_price - v[i]);
}
else {
max_price = v[i];
}
}
cout << "#" << test_case << " " << res << "\n";
}
return 0;
}
문제 풀이 결과
