SWEA D2 문제이다.
D2난이도를 보려고 풀었는데 한 번에 안풀려서 당황했다.. 큼
우선, 최대 가격일 때 팔아야 하고, 이후에 또 물건이 남아 있다면 그 중 최대 가격일 때 다시 판매해야 한다.
예를 들어,
가격이 1 1 3 1 2로 주어진다면, 전체에서 최댓값은 3이다.
그러면 첫째 날과 둘째 날에 구매한 후, 셋째 날에 판매하면 된다.
이렇게 셋째 날까지 총 4의 이익을 얻는다.
그다음, 넷째 날 이후의 가격에서 다시 최댓값을 찾는다.
이 경우, 다섯째 날이 최댓값이므로 넷째 날에 구매 후 다섯째 날에 판매하면 된다.
이때 1의 이익이 추가된다.
생각 1
이런 로직으로 생각해 max_element 함수를 사용해 앞에서부터 진행하며 최대값인 인덱스 전까진 구매하고, 최대일 때 판매한 뒤, 이후 범위에서 다시 최대값을 업데이트했다.
하지만 max_element를 너무 자주 쓰는 것 같아 조금 찝찝한 풀이였다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char** argv)
{
int test_case;
int T, N, maxIndex, answer;
vector <int> future;
vector <int> tmp;
cin>>T;
for(test_case = 1; test_case <= T; ++test_case)
{
cin>>N;
future.resize(N,0);
for(int i=0;i<N;i++){
cin>>future[i];
}
tmp.clear();
maxIndex=0; answer=0;
maxIndex=max_element(future.begin(), future.end()) - future.begin();
for(int i=0;i<N;i++){
if(i<maxIndex){
tmp.push_back(future[i]);
}
else if(i==maxIndex){
for(int t:tmp){
answer+=future[i]-t;
}
tmp.clear();
maxIndex=max_element(future.begin()+i+1, future.end())- future.begin();
}
}
cout<<"#"<<test_case<<" "<<answer<<endl;
}
return 0;
}시간 초과도 아니고 Fail(오답) 메시지가 떴다..
생각 2
인터넷에서 다른 풀이를 참고해 보았다.
생각 자체는 비슷했지만, 탐색을 아예 맨 뒤에서부터 시작하면 max 변수만 업데이트하면서 진행할 수 있다는 점을 알았다!
시간 복잡도를 개선하려면 많은 고민이 필요하구나..
그런데..
그렇게 작성한 코드도 예상 외로 Fail(오답)이 나오는것이다....
생각 3
놀랍게도 원인은 answer 변수의 자료형에 있었다. int가 아닌 long long을 사용해야 했다...
long long으로 변경하니 드디어 PASS!
최종 코드는 아래와 같다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(int argc, char** argv)
{
int test_case;
int T, N, max;
long long answer;
vector <int> future;
cin>>T;
for(test_case = 1; test_case <= T; ++test_case)
{
answer=0;max=-1;
cin>>N;
future.resize(N,0);
for(int i=0;i<N;i++){
cin>>future[i];
}
for(int i=N-1;i>=0;i--){
if(future[i]>max){
max=future[i];
}
else{
answer+=max-future[i];
}
}
cout<<"#"<<test_case<<" "<<answer<<endl;
}
return 0;
}생각 1의 코드도 answer의 자료형을 long long으로 바꾸니 PASS였다.
그래도 이건 제한 시간이 길어서 가능한 것!
시간 복잡도에 항상 유의하며 잘 공부하자.
1,000,000일 동안 매일 10,000원에 가깝다면
1,000,000 * 10,000 = 10,000,000,000 (100억)이다...! 워~~
근데 오버플로우라고 안뜨고 오답이라고 뜨다니 너무하다
long long 정리
-
int- 32비트
- 범위: -2,147,483,648 ~ 2,147,483,647 (약 21억)
-
long long- 범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
