[백준/C++] 알고리즘 11501번 - 주식

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 11501번 - 주식을 풀어보도록 하겠습니다.

 

 

https://www.acmicpc.net/problem/11501

 

 

[문제 접근]

처음 읽었을 때 어떤 알고리즘 개념이 들어있는지 정확히 파악이 되지 않았습니다.

그러나 최대 이익을 얻기 위해 최적의 해를 대략 생각해보아야 했기 때문에 그리디 알고리즘이라고 생각했습니다.

N은 백만이하이고, 시간제한은 5초여서 N^2풀이는 불가능합니다.

이 부분을 명확히 하지 않고 처음에 풀이를 진행해서 시간초과를 떴습니다. 

 

 

[풀이 전략]

첫번째 풀이 - 실패

첫번째로 최고 가격을 알아내고, 그 이전까지는 무조건 매입을 했습니다.

다음 인덱스에서 두번째로 최고 가격을 찾고 그 이전까지 무조건 매입을 했습니다.

이런 식으로 인덱스 마지막에 도달할때까지 반복했습니다.

최고 가격을 알아내기 위해 max_element를 사용했는데 이 함수의 시간복잡도는 O(N)입니다.

진행할수록 연산은 줄어들지만 최악의 경우 N+N-1 + N-2 + N-1 .... +1 => O(N^2)이 됩니다.

 

두번째 풀이 - 성공 

거꾸로 접근을 시도했습니다.

max라는 변수를 두어 가장 마지막의 원소로 초기화했습니다.

역순차로 접근하면서 max보다 작으면 계속 샀습니다.

max보다 크다면 max를 업데이트하고 건너뛰엇습니다.

다시 역순차로 접근하면서 업데이트된 max보다 작으면 계속 샀습니다.

인덱스가 0일때까지 계속 진행했습니다.

 

[코드]

첫번째  풀이 - 실패 

#include <iostream>
#include <algorithm>
using namespace std;

int t , n ;

int day[1'000'001];

int cnt ;
long long totprice ; 
long long result ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> t ;

    while(t--){
        cin >> n ;
        fill(day,day+n, 0);
        result = 0 ;
        for(int i = 0 ; i < n ; i++){
            cin >> day[i];
        }
            int st = 0 ;
            int en = 0 ;
        while (1)
        {   
            if(st == n) break;
            en = max_element(day+st,day+n) - day ;
            if(en == n) break;
            if(st == en) {st = en+1 ; continue;}
            
            totprice = 0 ;
            cnt = 0 ;

            for(int i = st ; i < en ; i++){
                cnt++;
                totprice += day[i];
            }
            result += day[en]*cnt - totprice;
            st = en+1;
        }
            cout << result<< '\n' ;
    }
 
}

 

두번째 풀이 - 성공

#include <iostream>
#include <algorithm>
using namespace std;

int t , n ;

int day[1'000'001];

int cnt ;
long long totprice ; 
long long result ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> t ;

    while(t--){
        cin >> n ;
        fill(day,day+n, 0);
        result = 0 ;
        for(int i = 0 ; i < n ; i++){
            cin >> day[i];
        }
        int maxV = day[n-1];
        int cnt = 0 ;
        for(int i = n-2 ; i >= 0 ; i--){
            if(maxV < day[i]) { maxV = day[i] ; continue;}
            result += (maxV-day[i]);
        }

            cout << result<< '\n' ;
    }
 
}

 

[배울 점]

- 거꾸로 생각하는 사고방식 탑재하기