[알고리즘] 1859. 백만 장자 프로젝트

 

0. 문제

 

D2 level

SW Expert Academy

 

---

1. 제출

 

가. 실패

#include<iostream>
#include<vector>
//#include<cstdio>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        int n;
        vector<int> v;
        long long ret = 0;
        cin >> n;
        for(int i = 0; i < n; i++){
            int tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
        while(true){
            //1. 전체의 최고점을 찾는다.
            int max = 0;
            for(int i=1; i<v.size(); i++){
                if(v[max] <= v[i]) max = i;
            }
            //2. 최고점이 시작점이라면 지금까지의 ret를 출력하고 끝낸다.
            if(max == 0){
                cout << "#" << test_case << " " << ret << endl;
                v.clear();
                break;
            }
            //3. 최고점의 index까지 이득을 ret에 더한다.
            for(int i = 0; i < max; i++){
                ret += v[max] - v[i];
            }
            //4. 최고점을 포함해 최고점까지 배열에서 삭제한다.
            v.erase(v.begin(), v.begin() + max + 1);
            // 5. 1번에서부터 반복한다.
        }
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.

 

제시된 코드의 문제점

 

 

최고 가격이 배열의 첫 번째에 위치할 경우 그 이후의 모든 데이터는 확인되지 않고 바로 종료되므로, 최고 가격 이후의 다른 날짜들에서 발생할 수 있는 이익을 놓칠 수 있습니다.

 

 

• 예시

1
5
5 1 3 2 4

제시된 코드는 첫 번째 날짜의 가격이 5로 가장 높으므로 바로 이 테스트 케이스를 종료하게 됩니다.

 

그러나 2번째와 3번째 날에 1과 3에 각각 구매하여 5번째 날에 4에 판매하면 이익은 4입니다.

 

따라서 최적의 해는 4이지만 제시된 코드는 0을 출력하게 됩니다.

 

 

---

나. 수정

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

int main() {
    int T;
    cin >> T;

    for (int tc = 1; tc <= T; ++tc) {
        int N;
        cin >> N;

        vector<long long> prices(N);
        for (int i = 0; i < N; ++i) {
            cin >> prices[i];
        }

        long long max_price = prices[N-1];
        long long profit = 0;

        // 뒤에서부터 앞으로 이동하면서 이익 계산
        for (int i = N-2; i >= 0; --i) {
            // 현재 날짜의 매매가가 최대 가격보다 낮으면
            if (prices[i] < max_price) {
                profit += max_price - prices[i];
            }
            // 현재 날짜의 매매가가 최대 가격보다 높으면 최대 가격 갱신
            else {
                max_price = prices[i];
            }
        }

        cout << "#" << tc << " " << profit << endl;
    }

    return 0;
}

 

해결 방안

 

최고 가격이 배열의 첫 번째 위치에 있더라도 그 이후의 날짜들을 검사하여 이익을 계산해야 합니다.

 

배열에서 데이터를 삭제하는 대신, 인덱스를 이동시켜서 이후의 데이터를 검사하도록 코드를 수정할 수 있습니다.

 

또는, 처음부터 뒤에서부터 순회하는 방식을 사용하는 것이 더 간결하며 효율적입니다.

 

이 방법을 사용하면 최고 가격을 찾을 필요 없이 뒤에서부터 순회하면서 현재 날짜의 가격과 이전 날짜의 가격을 비교하여 이익을 계산할 수 있습니다.

 

---

 

• 23년 11월 17일 추가

다 똑같은데 왜 prices를 배열 prices[1000000];가 아닌 vector로 선언해야 하는가?

 

일단 배열로 선언하면 정상적으로 동작하지 않는다.

 

앞서 메모리와 관련해서 정리한 적이 있다.

[C++] 메모리 할당

 

 

기준	long long prices[1000000]; 사용시	vector<long long> prices(n); 사용시
메모리 할당	스택 메모리에 고정 크기 할당 (1,000,000 * 8바이트)	힙 메모리에 동적 크기 할당 (n * 8바이트)
메모리 점유율	최대 4MB (메모리 낭비 가능성 있음)	필요한 만큼만 사용 (메모리 효율적)
오버플로우 위험	스택 오버플로우 가능성 높음	스택 오버플로우 위험 낮음 (힙 메모리 사용)

 

대부분의 시스템에서 기본 스택 크기는 배열 크기보다 훨씬 작습니다. 따라서, 이 방법으로 큰 배열을 선언하면 스택 오버플로우를 일으킬 수 있습니다.

 

힙은 스택보다 훨씬 큰 메모리 공간을 가지고 있기 때문에, 큰 데이터 구조를 저장하는 데 적합합니다.

 

그동안 큰 용량의 배열을 문제없이 선언할 수 있었던 이유는 전역변수로 선언했기 때문이다! 오옷!

 

큰 용량을 차지하는 데이터를 저장하기 위해서는 동적으로 관리되는 자료구조를 사용하던지, 전역으로 선언해야한다.

 

실제로 문제에서 사용가능한 메모리의 최대 크기를 언급하기도 했다.