[백준 11501번] 주식 (Python)

백준 11501번과 자료구조 과목 학습 후 정리한 포스팅 입니다.

이번 포스팅에서는 백준 11501번에 대해 학습합니다.

https://www.acmicpc.net/problem/11501

11501번: 주식

I) 문제

 

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

II) 입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

III) 출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

IV) 트러블 슈팅

기능을 정리하면 다음과 같이 생각할 수 있다.

price[day]를 day일의 주식 가격이라고 하면

1. price[day] < price[day+1]: 주식을 산다.

2. price[day] > price[day+1]: 주식을 판다.

3. price[day] = price[day+1]: 아무것도 안 한다.

 

🍀하지만 price[day] > price[day+1]이어도 price[day] < price[someday] 일 수 있다. (단, day < someday)

-> price[day] < price[someday]인 someday가 존재하면 day에 사서 someday에 팔면된다. 

이는 시간복잡도가 O(N^2)이므로 적합하지 않다.

매 순간 최선을 선택하는 그리디 알고리즘 활용 측면에서도 적합하지 않다

그래서 주식 값 리스트인 price에 뒤부터 접근한다

-> 약간 재벌집 막내아들 동포청년 느낌 ㅋ

V) 코드

# 주식 하나를 산다.
# 원하는 만큼 가지고 있는 주식을 판다. 
# 아무것도 안한다.

import sys
input = sys.stdin.readline

t = int(input()) # 테스트 케이스 개수 T
# 최적의 해를 보장해야하지 않을까?
for i in range(t):
    day = int(input()) # 날의 수를 나타내는 자연수 N
    
    price = list(map(int, input().split())) # 날 별 주가를 나타내는 자연수 N
    profit = 0 # 이익을 나타내는 변수
    last =  price[-1] # 마지막 날 주식의 가격, 초기 팔아야 하는 값을 마지막 날로 설정
    
    for j in range(day-1,-1,-1): # 거꾸로 확인하는 코드    ex) 1 2 3 4 -> 4 3 2 1        
        if price[j] < last: # N번째 날 주식이 증가하면 (N번째 날 - 오늘 주식)만큼 이득이 생긴다.
            profit = profit + last-price[j]  # 기존 이익 + 새로운 이익
        else: 
            last = price[j] # 팔아야 하는 날을 변경한다. 왜? price[i] > last 이니까~
            
    print(profit)

 

 

<Summary>

- 리스트를 거꾸로 생각하여 접근

- 리스트 순서를 바꾸는 방법 (Python)

 

*유의사항

- 알고리즘 공부 중인 인공지능공학과 학부생이 공부하여 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.