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

1859. 백만 장자 프로젝트

1차원의 배열을 받아서 최대의 이익을 계산하는 문제입니다.

하루에 1만큼 구매 가능하고 판매에 제한은 없습니다.

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

[테스트 케이스 01]

첫째날 10 둘째날 7 셋째날 6입니다.

첫째날이 가장 비싼 날이고 이후에 팔아도 이득이 없기 때문에 사지 않는 것이 이득입니다.

[테스트 케이스 02]

둘째날은 3 5 9 가 주어집니다.

마지막 날이 가장 비싸기 때문에 첫 째날 둘째날 하나씩 구매하고 마지막 날에 파는 것이 이득입니다.

(9 - 3) + (9 - 5) = 10

9*(1+1) - (3 + 5) = 10

[테스트 케이스 03]

1 1 3 1 2 이 주어졌을 때, 최대값이 끝에 존재 하지 않습니다.

이런 경우는 최대 값까지 계산하고 판매하기 때문에 이 뒤에 다시 구매와 판매를 해야합니다.

---

생각해보기

최대 이익을 위한 거래 순서는 물건은 값을 알고 구매하고 마지막에 팝니다.

만약 주어진 배열의 가장 마지막 값이 최대값이면 처음부터 읽어서 순서대로 진행해도 되는데, 중간에 최대값이 주어지는 경우에는 팔고 나서는 그 다음 인덱스부터 새로 사고 팔아야합니다.

1, 1, 2, 3, 5, 3, 4, 2 

여기서 5,  이전까지 산 값을 5, 에 팔고 3, 을 4, 에 팔고 2  는 구매해도 팔 날이 없기 때문에 못 팝니다.

이렇게 하면 너무 복잡해집니다. 최대 값이 중간에 존재한다면 인덱스를 뒤부터 출력해서 최대값을 저장하고 다음 수가 저장한 최대값 보다 크거나 같으면 다시 저장하고 작으면 최대값 빼기 해당 수를 출력합니다.

---

풀이

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

# T만큼 반복
for tc in range(1, T+1):
    # 자연수 N의 개수 입력
    N = int(input())
    # N 리스트 입력
    N_list = list(map(int, input().split()))

    # N_list의 마지막 값을 최대값으로 설정
    max_value = N_list[-1]
    # 이익 변수 초기화
    profit = 0

    # N-2번째 인덱스부터 0번째 인덱스까지 1씩 감소하면서 반복 순회
    for i in range(N-2, -1, -1):
        # 만약 현재 매매가가 최대값보다 크면 최대값을 변경
        if N_list[i] >= max_value:
            max_value = N_list[i]
        # 현재 매매가가 최대값보다 크지 않으면 차익을 profit 변수에 더해준다
        else:
            profit += max_value - N_list[i]

    # 결과 출력
    print('#{} {}'.format(tc, profit))

N = int(input()) # 전체 TC 갯수
for i in range(N): # TC마다
    M = int(input()) #배열의 길이 (안쓰임)
    answer = 0 #출력할 정답
    arr = list(map(int, input().split())) #배열 입력 받기
    sellPrice = 0 #현재 판매가격(최댓값)

    for val in arr[::-1]: # 배열 거꾸로 순회
        if val >= sellPrice: #현재 값이 최댓값보다 크거나 같다면
            sellPrice = val #최댓값 업데이트
        else:
            answer += sellPrice - val #아니라면 정답값에 가격차이를 더한다. (현재 값에 구매해서 최댓값에 판다)
    print("#", i + 1, " ", answer, sep="") #출력 양식에 맞춰서 출력

---

[형광펜]

 #ffd77f #6acd95 #cce8ff

#ccd1ff #8ecaee #e7a29b

#ffe99c #f7bdc3 #b7ddc8

#b7e0d8 #caadd2 #f3eb7f