[SEA - Python] 1859. 백만 장자 프로젝트

7월 13일에 진행되는 '삼성전자 DX부문 하계 대학생 S/W 알고리즘 역량 강화 특강'에 참여하기 위해 앞으로 일주일 간은 SEA에서 알고리즘 문제를 풀어보려 한다.

문제 설명

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.
다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.
다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다. 예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.

입력

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

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

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

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

출력

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

입력
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력
#1 0
#2 10
#3 5

Solution

처음 문제를 보고 DFS로 풀어야 하는건가, 완전탐색으로 풀어야 하는 건가 헷갈렸다.

그러나 문제 난이도가 D2인 점을 봤을 때 더 간단히 푸는 방법이 있을 것 같아서 좀 더 고민했다.

아무리 머리를 굴려도 답이 나오지 않아서 문제에 달린 댓글을 잠깐 참고했다.

힌트는 바로 맨 뒤에서 부터 계산하기 였다. 뒤에 있는 숫자보다 앞에 있는 숫자가 작다면 그 차(difference)가 이득을 본 값일 것이고, 숫자가 더 크다면 연산을 안하고 그 숫자를 기준으로 잡으면 되기 때문이다.

이 힌트를 얻어 내가 고안해낸 방법이다.

1. 리스트의 맨 뒤부터 반복문을 돌린다.
2. 맨 뒤에 위치한 숫자가 기준이 된다. (tmp 변수에 할당)
3. 다음 반복문에서 등장한 숫자가 tmp보다 크다면 tmp를 그 숫자로 초기화해준다.
4. 다음 반복문에서 등장한 숫자가 tmp보다 작다면 tmp에서 그 숫자를 마이너스 한 값을 answer에 저장한다.
5. 끝까지 반복문을 돌리고 최종적으로 연산된 answer 값을 출력한다.

Code

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    test_count = int(input())
    answer = 0
    case = list(map(int, input().split()))
    case.reverse()
    tmp = 0
    for i in case:
        if i > tmp:
            tmp = i
        answer += (tmp - i)
    print(f"#{test_case} {answer}")