1859. 백만장자 프로젝트

📕 문제

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

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

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

    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의 이익을 얻을 수 있다.

---

🤔Idea

입력에 주어진 N에 관한 조건을 보고 반복문이 많이 돌 수록 시간 복잡도 측면에서 불리해질 것이라는 생각이 들었다.

 

가장 처음 생각했던 방법은 첫 날부터 매수를 해가며 탐색해서 가장 이익이 큰 방법을 찾도록 하는 것이었다.

이렇게 접근할 시 for문을 두 번 돌아야 한다는 치명적인 단점이 있었다.

 

하지만 문제에서 주어진 것 처럼 미래를 보는 능력으로 우리는 매매가를 알고 있기 때문에뒤에서부터 순차적으로 계산 해 오는 방법을 선택할 수 있다.맨 마지막 날을 최대값으로 지정하고 거꾸로 순회하며 현재값이 최대값보다 작을 경우 매수, 현재값이 최대값보다 클 경우최대값을 변경하는 방식을 생각했다.

 

---

✏️ Solution

 

#테스트 케이스 개수 입력
T = int(input())

#T만큼 반복
for tc in range(1, T+1):
	#자연수 N의 개수 입력
    N = int(input())
    #N 리스트 입력
    N_list = list(map(int, input().split()))
    
    #리스트의 마지막 값을 최대값으로 설정
    max_value = N_list[-1]
    profit = 0
    
    #리스트의 끝에서부터 1씩 감소하며 순회
    for i in range(N-2, -1, -1)
    	if N_list[i] >= max_value : 
        	max_value = N_list[i]
		else:
        	profit += max_value - N_list[i]
 
 #결과 출력
 print("#{} {}".format(tc, profit))

엉엉 이번 싸피는 망한것 같다

이게 무슨 D2야 실화야? ㅠ_ㅠ