[SWEA] 백만 장자 프로젝트(1859) - Python(리스트 구현)

1차원 배열로 된 매매가를 입력받아, 최대 이익을 출력하는 문제이다.

 

SW Expert Academy

 

---

테스트 케이스

 

[TC1]

입력 : 10 7 6

정답 : 0

해설 : 아무 것도 사지 않는 것이 최대 이익이다.

 

[TC2]

입력 : 3 5 9

정답 : 10

해설 : 1일과 2일에 각각 사서 3일에 판매하면 10 (9*2 - (3 + 5)) 이익이다.

 

[TC3]

입력 : 1 1 3 1 2

정답 : 5

해설 : 1일, 2일 구매 후, 3일에 판매 그럼 4 (3*2 - (1 + 1))이익, 4일 구매 후, 5일에 판매하여 1 (2*1 - 1) 이익이므로 총 5 이익이다.

 

---

해결과정

 

처음 문제를 풀며 주어진 개수에서 하나씩 줄여가며 ((현재 매매가 * 구매 개수) - 총 구매 가격) 으로 이익을 구하였다. 하지만, 이럴경우 앞에서 줄인 매매일에서 볼 수 있는 이득을 놓치게 된다.

그래서 맨 뒤 인덱스부터 시작하면서 최댓값을 비교하여 지금까지 저장한 최댓값보다 작으면 판매하고, 크면 최댓값을 갱신하고 넘어간다.

 

---

코드

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    answer = 0
    items = list(map(int, input().split()))
    max = 0
     
    for i in items[::-1]:
        if i >= max:
            max = i
        else:
            answer += max - i
    print(f'#{test_case} {answer}')

 

주석처리

T = int(input()) # TC 입력 받음
for test_case in range(1, T + 1): # TC 동안
    N = int(input()) # 연속된 N일
    answer = 0 # 정답
    items = list(map(int, input().split())) # 매매가를 받음
    max = 0 # 최댓값
     
    for i in items[::-1]: # 매매가를 뒤에서부터 순회
        if i >= max: # 현재 매매가가 최댓값보다 크면
            max = i # i를 최댓값으로
        else: # 현재 매매가가 최댓값보다 작으면
            answer += max - i # 정답에 이익(최댓값 - 매매가)을 추가
    print(f'#{test_case} {answer}')