앞에서부터 주식이 가장 비싼 날에 판매하는 식으로 구하면 더 복잡해진다
그니까 [3 5 9] 날로 입력받았고 3 다음에 더 떨어질지 오를지 예측하는 것 보다
뒤에서부터 구하는게 더 낫다는 이야기.
그래서 max값보다 떨어졌으면 이익을 더해주는 식이 된다.
처음엔 max값과 index값을 찾아서 계산해주는 식으로 구했는데,
[1 1 3 1 2]로 입력받았을 경우엔 max=3, index=2가 되어 index 0,1에 대해서만 구해 5로 출력해야하지만 4로 출력해서 안됨
그냥 뒤에서부터 계산하면서 v[i]가 max보다 크면 max에 대입해주면 되고,
아니면 result에 더해주면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>
#include <vector>
using namespace std;
int main() {
cout.tie(NULL);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int T, N;
cin >> T;
vector<int> v;
while (T--) {
cin >> N;
long long result = 0;
for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
v.push_back(tmp);
}
int max = v.back();
for (int i = v.size() - 2; i >= 0; i--) {
if (v[i] > max) {
max = v[i];
}
else {
result += (max - v[i]);
}
}
cout << result << '\n';
v.clear();
}
return 0;
}
|
cs |
코드엔 따로 올리지 않았지만 vector말고 int 배열로 선언하고, max값을 n-1로 설정해주면
굳이 38줄처럼 clean해주지 않아도 된다.
그럼 메모리도 시간도 좀 더 효율적이다.