사용자 도구

사이트 도구


ps:problems:boj:11501

주식

ps
링크acmicpc.net/…
출처BOJ
문제 번호11501
문제명주식
레벨실버 2
분류

그리디

시간복잡도O(t*n)
인풋사이즈t<=?, n<=1,000,000
사용한 언어Python
제출기록169696KB / 3224ms
최고기록2584ms
해결날짜2021/12/31

풀이

  • 가장 큰 이익을 보는 방법은, 매일 주식을 사고, x번째 날에 산 주식을 x번째날 이후에 가장 가격이 비싼 날에 파는 것이다.
  • 하지만, 모든 x에 대해서 x번째날 이후에 가장 가격이 비싼 날을 구하는 것은 비효율적이다.
  • a0(=전체 구간에서 가장 가격이 비싼날)을 찾고, a1(=a0 이후에서 가장 가격이 비싼날). a2,…, ax를 구한 뒤에, (0,a1)까지의 주식은 a1날에 팔고, (a1,a2) 까지의 주식은 a2에 팔고, .. 하는 방법이 가능하다. 하지만 a_i를 찾을때, a1을 구하고, 남은 구간에서 a2를 구하고 하는 식으로 찾으려고 하면 O(n^2)이 걸린다.
  • 더 효율적인 방법은 뒤에서부터 이터레이션을 하면서 a_x, a_x-1, …, a1 을 역순으로 찾는 것이다. a_x, a_x-1, …, a1를 다 갖고 있을 필요도 없고, 그냥 최고 가격을 유지하면서 있으면서, 현재 가격이 최고 가격보다 작으면 그 차액만큼을 더해주고, 최고 가격보다 크면 최고가격을 갱신해주는 식으로 처리하면 된다. 이렇게 하면 O(n)에 계싼이 가능하다.

코드

"""Solution code for "BOJ 11501. 주식".

- Problem link: https://www.acmicpc.net/problem/11501
- Solution link: http://www.teferi.net/ps/problems/boj/11501

Tags: [Greedy]
"""


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())  # pylint: disable=unused-variable
        prices = [int(x) for x in input().split()]

        answer = 0
        max_price = 0
        for price in reversed(prices):
            if price <= max_price:
                answer += max_price - price
            else:
                max_price = price

        print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U G E G X
 
ps/problems/boj/11501.txt · 마지막으로 수정됨: 2021/12/31 09:01 저자 teferi