SWEA 1859. 백만 장자 프로젝트

• 문제 링크 : 1859. 백만 장자 프로젝트

---

문제 요약

앞으로 N일 동안의 물건 가격을 모두 알고 있다. 하루에 물건은 최대 1개만 살 수 있고, 파는 것은 하루에 몇 개든 할 수 있다. 이 조건에서 사고팔아 얻을 수 있는 최대 이익을 구한다. 예를 들어 가격이 1, 2, 3이면 첫날과 둘째 날에 하나씩 사서 셋째 날에 모두 팔아 (3-1) + (3-2) = 3의 이익을 얻는다.

---

1. 문제 해석

정리하면, N일 동안의 가격을 미리 알고 있고 하루에 최대 한 개를 살 수 있으며 파는 것은 언제든 원하는 만큼 할 수 있을 때, 얻을 수 있는 최대 이익을 구하는 문제다.

처음 떠오르는 방법은 날마다 “이 날 사서 이후 언제 팔면 가장 이득인가”를 찾는 것이다. 그런데 이 질문의 답은 단순하다. 오늘 산 물건은 오늘 이후 가장 비싼 날에 파는 것이 가장 이득이다. 판매에는 제한이 없으므로 여러 날에 산 물건을 같은 날 한꺼번에 팔아도 된다. 따라서 각 날 i에 대해 이후의 최고가를 max_future라 하면, 오늘 가격이 그보다 낮을 때 사서 max_future - price[i]만큼 이익을 얻고, 그렇지 않으면 사지 않으면 된다.

날마다 이후의 최고가를 새로 찾으면 O(N²)이다. 대신 뒤에서부터 거꾸로 보면서 지금까지 본 최고가를 들고 가면, 각 날의 “이후 최고가”를 한 번의 순회로 알 수 있다.

예를 들어 가격이 3, 1, 4, 2라면, 뒤에서부터 볼 때 마지막 날 2가 첫 최고가다. 셋째 날 4는 최고가보다 비싸므로 사지 않고, 최고가를 4로 바꾼다. 둘째 날 1은 4에 팔아 3의 이익을, 첫째 날 3은 4에 팔아 1의 이익을 얻는다. 합은 3 + 1 = 4다. 첫째 날에 사서 둘째 날에 파는 것처럼 바로 다음 날만 보면 이익이 없지만, 셋째 날까지 들고 가면 이익이 생긴다.

---

2. 문제 풀이

#include <iostream>
using namespace std;
int N;
int price[1000000];
long long solution(){
    long long answer=0;
    int max_price=price[N-1], sum=0, count=0;
    for(int i=N-2;i>=0;--i){
        if(price[i]>=max_price){
            answer += max_price * count - sum;
            max_price=price[i];
            count=0; sum=0; continue;
        }
        count++;
        sum+=price[i];
        if(i==0){
            answer += max_price * count - sum;
        }
    }
    return answer;
}

int main(int argc, char** argv) {
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
        for(int i=0;i<N;++i){
            cin >> price[i];
        }
        cout << "#" << test_case << " " << solution() << "\n";
    }
    return 0;
}

---

코드 읽기

solution()은 위의 생각을 구간 단위로 계산한다.

• max_price는 지금까지(뒤에서부터) 본 최고가이고, 마지막 날 가격으로 시작한다.
• 최고가보다 싼 날을 만나면 바로 이익을 더하지 않고, 그날을 산 날로 세면서(count++) 가격을 sum에 더해 둔다.
• 최고가 이상인 날을 만나면, 지금까지 모은 구간을 그 최고가에 한꺼번에 판다. 이익은 max_price * count - sum이다. 각 날의 이익 max_price - price[i]를 구간 안에서 모두 더한 것과 같다. 그 뒤 최고가를 새 가격으로 바꾸고 구간을 비운다.
• 첫째 날(i == 0)까지 왔는데 최고가 이상인 날을 만나지 못했다면 남은 구간을 정산한다. 첫째 날이 최고가 이상이라면 위의 분기에서 이미 정산되고 continue로 빠지므로 두 번 더해지지 않는다.

---

복잡도

배열을 뒤에서부터 한 번 훑으므로 시간은 O(N), 가격 배열 외의 추가 공간은 O(1)이다.

---

자료형에서 주의할 점

answer는 long long이지만 max_price * count는 int끼리의 곱이라, 그 결과가 long long으로 바뀌기 전에 int 범위에서 먼저 계산된다. sum도 int다. 배열 크기를 1,000,000으로 잡은 것처럼 일수가 백만에 가깝고 가격이 수천 이상이면 곱이나 합이 int 범위(약 21억)를 넘는다. 안전하게 하려면 sum을 long long으로 선언하고 1LL * max_price * count처럼 곱하기 전에 한쪽을 long long으로 바꾸면 된다. 위 코드는 원래 제출한 그대로 두었다.

같은 아이디어를 구간 없이 쓰면 다음처럼 더 짧아진다. 날마다 바로 이익을 더하는 형태라 정산 분기가 필요 없다.

long long solution() {
    long long answer = 0;
    int max_price = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (price[i] > max_price) max_price = price[i];
        else answer += max_price - price[i];
    }
    return answer;
}