[코딩테스트] SWEA 1859 백만장자 프로젝트 - C++

Eugene CHOI·2021년 3월 28일

Coding Test

목록 보기

2/7

SW Expert Academy의 1859번 백만장자 프로젝트 문제는 난이도 D2에 들어가면 처음 만날 수 있는 문제입니다.
D2 난이도의 첫 문제임에도 다른 문제보다 난이도가 높습니다.
그래서 그런지 문제의 주인공 원재를 원망하는 댓글창이 재미있습니다.

Problem

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

Approach

이 문제는 원료를 싸게 사서 비싸게 팔아 최대한의 이익을 챙기는 문제입니다.
쉽게 생각하면 다음과 같은 알고리즘을 생각해 볼 수 있습니다.

오늘보다 내일 가격이 더 비싸다면 오늘 물건을 산다.

오늘보다 내일 가격이 더 싸다면 모든 물건을 팔거나 가만히 있는다.

마지막 날까지 왔지만, 물건이 남았다면 모든 물건을 판매한다.

하지만 다음과 같이 계속 감소 하다가 어느날 최고가가 나온다면 최대 이익을 얻지 못하게 됩니다.

따라서 모든 날짜 중에서 최대가격이 언제인지 계산하는 과정이 필수적입니다.
그러면 생각해 볼 수 있는 두 번째 알고리즘은 다음과 같습니다.

1. 현재 이후로 언제 최대가격을 가지는지 계산합니다.
2. 최대가격을 가진 날짜가 오늘과 같다면 가진 물건을 판매합니다.
3. 날짜가 같지 않다면 무조건 물건을 구매합니다.

Caution

날짜는 1,000,000일까지, 금액은 최대 10,000원까지 주어질 수 있습니다.
이 문제에서 얻을 수 있는 가장 큰 이익을 생각해보면 1,000,000일이 주어지고. 매일 1원만큼 물건을 구매하고 마지막 날 10,000원에 판매한다면 총 $9999\times999,999=9,998,990,001$ 원의 이득을 얻을 수 있습니다.
이 값은 4byte int의 범위인 2,147,483,647을 넘어서는 overflow가 일어날 수 있기 때문에 누적 이득을 저장하는 변수는 최소 long int 이상이 되어야 합니다.
빠른 입출력을 위해 cin보다 scanf를 활용합니다.
지역변수는 메모리 영역 중 Stack 영역에 저장되고, 전역변수는 Data 영역에 저장이 됩니다. 지역변수의 크기를 과도하게 잡을 경우 Heap 메모리 영역을 침범하는 문제가 발생할 수 있습니다.
큰 배열을 사용하는 경우에는 문제가 있지 않는 이상 전역으로 할당하는 것이 좋습니다.

Implement

Thinking1: Find Max

최대가격을 가진 이후 날짜를 만나면 새로운 최대가격을 가진 날짜를 계산하여 판매, 구입하는 상식적인 방법으로 접근한 알고리즘입니다.

#include<iostream>
using namespace std;

int prices[1000000];

int max(int s, int e){
    int idx = s;
    for(int i = s; i < e; i++)
        if (*(prices + idx) < *(prices + i))
            idx = i;
    return idx;
}

int main(int argc, char** argv){
	int i, test_case, T, N;
	cin>> T;
	for (test_case = 1; test_case <= T; ++test_case) {
        cin >> N;
    	long num_stock = 0, balance = 0;
        for (i = 0; i < N; i++) cin >> *(prices+i);
        int idx = max(0, N);
        
        for (i = 0; i < N; i++) {
            if (idx <= i) {
                idx = max(i + 1, N);
                balance +=  *(prices + i) * num_stock;
                num_stock = 0;
            }
            else {
                num_stock++;
                balance -= *(prices + i);
            }
        }
        if(num_stock) balance += prices[i] * num_stock;
        printf("#%d %ld\n", test_case, balance);
	}
	return 0;
}

Think2: Compute once

현재 코드는 날짜가 바뀔 때마다 전에 계산 했던 최대값을 다시 계산하기 위해 반복문을 돌며 많은 시간을 낭비합니다.

우리가 원하는 것은 그 날까지의 최대값이 아니라 그 날 이후의 최대값입니다.
배열의 뒤에서부터 차례대로 max값을 찾아가며 그 날의 최대값을 미리 배열에 저장하면 단 한 번만 for문을 반복하여 모든 날에서의 이후 max값을 찾을 수 있습니다.

#include<iostream>
using namespace std;
 
int prices[1000000], max_price[1000000];
 
int max(int N){
    int idx = N - 1;
    for(int i = N - 1; i >= 0; i--){
        if (*(prices + idx) < *(prices + i))
            idx = i;
        max_price[i] = idx;
    }
}
 
int main(int argc, char** argv){
    int i, test_case, T, N;
    cin>> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        scanf("%d", &N);
        long int num_stock = 0, balance = 0;
        for (i = 0; i < N; i++) scanf("%d", prices+i);
        max(N);
        int idx = max_price[0];
         
        for (i = 0; i < N; i++) {
            if (idx <= i) {
                idx = max_price[i + 1];
                balance +=  *(prices + i) * num_stock;
                num_stock = 0;
            }
            else {
                num_stock++;
                balance -= *(prices + i);
            }
        }
        if(num_stock) balance += prices[i] * num_stock;
        printf("#%d %ld\n", test_case, balance);
    }
    return 0;
}

Conclusion

실행 시간이 0.5초 정도 줄었습니다.
하지만 사실 이만한 메모리도, 코드도 쓰지 않고, 더 줄일 수 있습니다.
총 5일이 주어지고 각 가격이 다음과 같다고 가정합니다.

날짜: 1 2 3 4 5
가격: 1 4 2 3 7

위의 데이터에서 최대 이익을 남기는 방법은 아래와 같습니다.

마지막 날부터 시작합니다.

만약 5일 가격이 4일보다 낮다면 5일 가격에 4일 물건을 하나 팝니다.

만약 3일 가격이 5일보다 낮다면 5일 가격에 3일 물건을 하나 팝니다.

만약 2일 가격이 5일보다 높다면 그냥 넘어갑니다.

만약 1일 가격이 2일보다 낮다면 2일 가격에 1일 물건을 모두 팝니다.

이와 같은 방식으로 우리는 쉽게 최대 이익을 계산할 수 있습니다.
다시 알고리즘으로 표현해봅시다.

모든 날짜의 가격을 stock이라는 배열에 미리 저장한 다음부터 뒤에서부터 시작합니다.

마지막 날을 max로 합니다.

마지막 날 하루 전부터 현재 날짜 i일로 시작합니다.

첫째날이 될 때까지 다음을 반복합니다.

만약 max일 가격보다 i일 가격이 낮다면 max일 가격(판매가)에 i일 가격(구매가)을 뺀 금액을 balance에 더합니다.

아니라면 i일을 max일로 재설정합니다.

i = i - 1

#include<iostream>
using namespace std;

int stock[1000000];
int main(int argc, char** argv){
    int i, test_case, T, N;
    cin>> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        scanf("%d", &N);
        long balance = 0;
        for (i = 0; i < N; i++){
            scanf("%d", stock + i);
        }
        int max = i - 1;
        for (i -= 2; i >= 0; --i) {
            if (stock[i] <= stock[max]){
                balance += stock[max] - stock[i];
            }
            else{
                max = i;
            }
        }
        printf("#%d %ld\n", test_case, balance);
    }
    return 0;
}