백만장자 프로젝트

SWExpert D2 백만장자 프로젝트

https : //swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

난이도 D2로 생각보다 어렵지 않은데, 정답률은 기괴하게 20%대를 기록하고 있다.
이는 놀랍게도 정답이 long long int 인데, 다들 int로 했기 때문!
나는,,, long long int 까지는 했으나, cout에 익숙해져 printf를 쓸 때 %lld를 안하고 %d를 해서 틀렸다.
댓글을 보지 않으려고 노력하다, test case 7까지는 맞는게 너무 이상해서 찾아보니 %lld를 쓰면 된다 하더이다...
로직은 생각보다 간단하다
문제: 원재는 연속된 N일 동안 물건의 매매가를 알 수 있다.
매일 1개씩만 사서, 최대한의 이득을 보자 (판매는 자유롭다)
ex 1) 3일 동안의 매매가가 1,2,3 이라면 처음 두 날에 구매하고, 마지막 날에 판매하면 2+1 = 3원의 이득이다
ex 2) 5일에 1 1 3 1 2 면 5원이다.

으레 그렇듯 SWExpert가 제공하는 Form

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main(int argc, char **argv)
{
    int test_case;
    int T;

    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {

모든 날의 매매가를 vector days에 담았다.
담을 때 max_index를 구했다.

        int N;
        int max_index = 0;
        int max = 0;
        int temp = 0;
        vector<int> days;
        scanf("%d", &N); //how many days
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &temp);
            days.push_back(temp);
            if (max <= temp)
            {
                max = temp;
                max_index = i;
            }
        }

가장 비싼날에, 모든 재고를 처분하고, 그 다음 가장 비싼 날에 또 재고를 처분한다.
이를 마지막 날까지 반복하면 된다

        //input done to days
        long long ans = 0;
        int curr = 0;
        while (true)
        {
            if (max_index == N - 1)
                break;                        //end point
            for (; curr <= max_index; curr++) //ans ++
                ans += (max - days[curr]);
            max = days[curr]; //max reset, find
            for (int i = curr; i < N; i++)
            {
                if (max <= days[i])
                {
                    max = days[i];
                    max_index = i;
                }
            }
        }

으레 그렇듯 마무리

        for (; curr <= max_index; curr++) //ans ++
            ans += (max - days[curr]);

        printf("#%d %lld\n", test_case, ans);
    }
    return 0; //정상종료시 반드시 0을 리턴해야합니다.
}

C++에서 30초라는 괴랄한 시간을 주기 때문에 성능은 거의 신경 안써도 된다고 생각하면 된다.
역순으로 받아서, vector에서 pop()해버리는 방식도 나쁘지 않아 보이는데,
위처럼 간단하게 끝낼 수 있을 것 같다.