1859. 백만 장자 프로젝트

D2 난이도에 정답률 25.71%....낮다.

처음에 아무리 생각해도 다 시간초과에 접근 방법이 생각이 안 나서....

탐색이 아닌 다른 방법을 생각해 보았으나!!!틀렷다...

그러나 힌트를 보고야 말았다..D2 주제에....

나의 접근 법이 비슷했으나 약간..? 어긋나 있었던 것이다.ㅜ,ㅠ

입력 받은 값 중에 최대값을 찾고, 그 최대값 까지 하루에 하나씩 산 후 최대 값에서 판다. 그리고 그 뒤에 입력이 더 남아 있으면 그 중에서 최대값을 찾아 최대값 까지 하나씩 산 후 최대 값에서 판다.

이런식...??시간초가 좀 길게 나와서 수정을 좀 해봐야 것다.

#include <stdio.h>
#include <string.h>
 
int arr[1000001];
long long total;
 
typedef struct
{
    int max;
    int pos;
}MAX;
 
 
MAX max;
 
void findmax(int num, int back)
{
    for (int i = num + 1; i < back; i++)
    {
        if (arr[i] > max.max)
        {
            max.max = arr[i];
            max.pos = i;
        }
    }
}
 
int main()
{
    int Test;
    scanf("%d", &Test);
 
    for (int i = 1; i <= Test; i++)
    {
        memset(arr, 0, sizeof(arr));
        int num, part=0;
        int count = 0;
        total = 0;
        max.max = 0;
        max.pos = 0;
        total = 0;
        scanf("%d", &num);
 
        for (int j = 0; j < num; j++)
        {
            scanf("%d", &arr[j]);
            if (arr[j] > max.max)
            {
                max.max = arr[j];
                max.pos = j;
            }
        }
 
        for (int j = 0; j < num; j++)
        {
            if (max.pos == j)
            {
                total += max.max*count - part;
                max.max = 0;
                max.pos = 0;
                count = 0;
                part = 0;
                findmax(j, num);
            }
            else
            {
                part += arr[j];
                count++;
            }
        }
 
        printf("#%d %lld\n", i, total);
 
    }
 
    return 0;
}