[Python][SWEA] 1859. 백만 장자 프로젝트 D2

🗒️ 파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1):
    N = int(input())
    lst = list(map(int,input().split()))
    u_lst = lst[::-1]

    max = u_lst[0]
    ans = 0
    for i in range(1,len(u_lst)):
        if u_lst[i] > max :
            max = u_lst[i]
        else :
           ans += (max-u_lst[i])

    print(f"#{tc} {ans}")

 

1.

(문제점)

0 인덱스에서 순차적으로 하면, 최대값이 계속 갱신될 수 있다는 생각을 하게된다.

최대값이 갱신되면, 과거의 최대값은 무용지물이 되어버린다.

(N의 범위가 1,000,000이기 때문에 2중 반복문은 안됨)

 

(해결책)

하지만 우리는 이미 어떤값들이 주어질지 알기때문에, 거꾸로 연산을 해주면 된다.  

거꾸로 연산에서 얻을수 있는 이득은 이전 인덱스를 생각 안해도 된다.

최대값이 갱신되면서 인덱스를 하나씩 나아가는데, 미래 인덱스와 크기만 비교해주면 된다.

 

2. 뒤에서부터 시작하고, 나아갈때마다 최대값을 갱신해준다.

 

3. 최대값이 갱신이 안되면, 그 값이 현재의 최대값이므로 현재 인덱스값과 빼준다.

 

(인덱싱을 편하게 하기위해 리스트를 거꾸로 뒤집었다.)

 

🧐 문제 코멘트

이 문제를 2번째 풀고있다.  처음에도 못풀었는데, 시간 지나고도 못 풀었다 ㅠㅠ 

우선 N의 범위로 할 수 있는게 한정된 것은 알겠는데, 어떻게 최대값을 계속 찾을지에 대해 고민했다.

좀 더 단순하게, 미래를 예측 할 수 있다고 했으니 이를 적극 활용하자.

---

📚 문제

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

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

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

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

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


[입력]

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

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

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

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


[출력]

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


[예제 풀이]

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.

2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.