[SW Expert Academy] 1859. 백만 장자 프로젝트 파이썬 정답 코드

 

SW Expert Academy

 

1. 문제 내용

 

 

2. 접근 방식

테스트 케이스

• 접근1: 최대 이익을 내기 위해선 오늘 산 물건의 가격보다 다음 날 가격이 더 높아야 한다.

따라서 10 7 6의 경우 날이 지날수록 가격이 떨어지기 때문에 애초에 구매하지 않아야 최대 수익 0을 낼 수 있다.

그렇다면 3 5 9의 경우는 어떨까? 3보다 5가 더 높기 때문에 바로 5에 팔아버리면 그 다음 날 9로 팔 수 있는 기회가 사라진다. 즉, 무작정 오늘에 비해 내일 가격이 더 비싸다고 팔면 최대 이익을 얻을 수 없다.

 

• 접근2: 매일 1개씩 사다가, 전체에서 가장 비싼 가격일 때 팔아야 한다.

1 1 3 1 2에서 가장 비싼 가격은 3이다. 따라서 가장 비싼 날이 되기 전까지 구매하다가 가장 비싼 3에 팔아버리고, 그 이후부터 다시 가장 비싼 가격인 2에서 팔면 최대 이익을 낼 수 있다.

 

코드로 생각하면 [1, 1, 3, 1, 2] 에서 가장 큰 값은 3이고, 인덱스는 2이다. 따라서 인덱스 2 전까지는 계속 구매하다가, 인덱스 2일 때 물건을 판다. 이후엔 리스트를 인덱스 2이후부터인 [1, 2]로 바꾼 후, 다시 가장 큰 값 2의 인덱스 전까지 물건을 구매하다가 2일 때 팔면 된다.

 

 

3. 정답 코드

• 리스트 슬라이싱

T = int(input())

for test_case in range(1, T + 1):
    n = int(input())
    data = list(map(int, input().split()))
    
    answer = 0
    
    while True :
        max_data = max(data)
        index = data.index(max_data)
        answer += ( max_data * index ) - sum(data[:index])
        
        if index == len(data) - 1 :
            break
            
        data = data[index+1:]
    print("#" + str(test_case), answer)