SWEA 1859 백만 장자 프로젝트 (핵심 : 맨 뒤에서부터 계산하기)

💡문제 분석 요약

• 사재기를 하기 위해서 사야할 때랑 팔아야할 때를 알아야함.
• 쉽게 말해서, 내가 지금 샀을 때보다 나중에 비싸게 팔 수만 있다면 무조건 사는 게 이득. 즉, 오늘보다 비싼 날이 뒤에 있기만 하면 구입.

💡알고리즘 설계

• 맨 뒤에서부터 max값을 업데이트해가면서 이익을 계산한다.
• 만약 .... max1 .... max2 이런식으로 있다고 해보자. max1 > max2라고 하면, 앞에서 산건 max1때 털어내겠고, 그럼 뒤에서 산건 max2때 털어낸다. 만약 max1 < max2라면 ?? 계속 들고있다가 max2때 딱 1번 털어낸다.
• 따라서 max2에 깃발 꽂고, 뒤에서부터 앞으로 계산해간다. max2부터 max1까지 있는 모든 물건 다사고 max2때 털어내면 되니까 이익 = max2 - element 이런식으로 차익을 계산하면 된다.

💡코드

T = int(input()) # 테스트 케이스 개수
for t in range(T):
    n = int(input()) # N일동안의 매매가
    prices = list(map(int, input().split()))

    max_price = 0  # 뒤에서부터 본 최대값
    income = 0  # 총 이익
    
    for i in range(n-1, -1, -1):
        if prices[i] > max_price: # 최대값이면 교체해줌
            max_price = prices[i]
        else: # 최대값 아니면
            income += max_price-prices[i] # 차액이 이익이니깐

    print(f"#{t+1}", income)

💡시간복잡도

• O(N) 맨 뒤에서부터 앞으로 딱 1번만 계산하면 되니까

💡 틀린 이유, 수정

• 접근법은 비슷하게 했는데, "뒤에서부터 계산"이라는 것을 떠올리지 못했다. 그래서 앞에서부터 계속 max 찾아가면서 슬라이싱해가려고 했는데, 그렇게 하면 매번 O(N)이 들고 비효율적인 것 같다.

💡 느낀점 or 기억할정보

• 맨 뒤에서부터 계산하기 ..... 이거는 꼭 알아가자.