SWEA D3 1859. 백만 장자 프로젝트

문제

---

솔루션

T = int(input())
for T in range(1,T+1):
    N = int(input())
    li = list(map(int,input().split()))
    li = li[::-1]
    profit = 0
    current=li[0]
    for i in li:
        if i<current:
            profit += (current - i)
        else:
            current = i
    print(f"#{T} {profit}")

---

알게된점

정답율 순으로 풀다가 쉬워서 제출순으로 봤더니 D2D3중 첫번째에 있었다.

문제를 이해하는데 생각보다 오래걸렸다.

 

미래의 가격 변동을 모두 알고 있다는 점을 이용해, 뒤에서부터 접근하는 방식으로 탐색하는것이 효율적이였다.

일반적으로 다음 날 가격을 모른다면 동적 계획법(DP)을 사용해 최적 해를 찾지만, 미래의 가격을 알고 있어 [::-1] 을 이용해 푸는 것이다.

    profit = 0
    current=li[0]
    for i in li:
        if i<current:
            profit += (current - i)
        else:
            current = i

• 초기 설정: li[0]을 최고 매도가 기준인 current로 설정
• 매수와 매도 판단: for문에서 각 날의 매매가 i를 current와 비교
  • 가격이 낮을 때: i < current로 current를 기준으로 i일에 매수하여 (current - i)의 이익, 이 이익을 profit에 더함
  • 가격이 높거나 같을 때: current를 업데이트해 새로운 매도일 기준을 설정

최대 이익을 내기 위해서는 물건을 매수할 때는 저렴하게, 매도할 때는 매수한 가격보다 비싸게 팔아야 한다. 이 과정에서 특정 가격을 기준으로, 더 높은 가격일 때는 판매하고 더 낮은 가격일 때는 매수하는 방식으로 진행하면 됐다.

 

구체적으로, 뒤에서부터 가격을 탐색하면서 당일의 가격이 이전 날보다 높다면 당일을 매도일로, 이전 날을 매수일로 정하여 차익을 계산한다. 만약 이전 날이 당일보다 비싸다면 그날은 매수하지 않고, 매도 기점을 전환해 다시 탐색한다.

이 과정을 리스트 끝에서 시작해 앞쪽으로 반복하면서 이익을 합산하면 최대 이익을 구할 수 있다.