1859. 백만 장자 프로젝트

문제를 처음 읽고 예전에 풀어봤던 느낌이 났었다. 그래서 문제를 풀고 백준을 찾아봤는데, 이 문제의 해결법과 같지는 않지만 가장 긴 증가하는 수열 시리즈 문제를 풀었을때와 구조가 비슷하다고 생각했다.

문제를 접근하는 방법은 다음과 같다. 핵심은 싸게 사서 비싸게 파는 것인데, 선형으로 탐색한다면 언제가 가장 비쌀지를 모르기 때문에 선형탐색을 한다면 파는 시점을 계속 수정해 나가야함을 생각할 수 있다.
예를 들어 1 1 2 1 3 이 있을때, 3에 모두 파는게 제일 현명한 선택이고,
만약 1 1 3 1 2 가 있다면 3에서 앞에서 샀던것을 팔고 2에서 3 이후에 산것을 팔면 된다.

그렇기 때문에 파는 시점의 위치에 따라서 언제 팔지가 정해지는데, 만약 뒤에서부터 바라본다면, 문제가 쉬워진다.
예를 들어 위의 1 1 3 1 2 예시에서 제일 뒤에서부터 (2에서부터) 앞으로 차례대로 탐색 했을 때, 2보다 큰 값이 나오기 전 까지는 계속해서 사들여도 된다.
만약 3이 나온다면 인덱스값을 바꿔주고 3 뒤에서부터 2까지 물건들을 정산하는 것이다.
위의 아이디어를 코드로 구현하면 된다.

t = int(input())
for _ in range(t):
    ans = 0
    n = int(input())
    arr = list(map(int,input().split()))
    idx = len(arr)-1
    for i in range(len(arr)-1,-1,-1):
        if arr[i] <= arr[idx]: ## 체크한 인덱스 값
            continue
        else:
            cnt = idx - i - 1
            temp_sum = sum(arr[i+1:idx])
            ans += (arr[idx] * cnt - temp_sum)
            idx = i
    temp_sum = sum(arr[0:idx])
    cnt = idx
    ans += (arr[idx] * cnt - temp_sum)
    print(f"#{_+1} {ans}")