[백준 11501][파이썬] 주식 (그리디, 재귀)

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

11501번: 주식

주식으로 벌어들인 이득이 최대가 되도록 하는 알고리즘을 작성하는 문제이다.

 

이득이 최대가 되려면 다음과 같은 과정을 거친다.

1. 주식 가격이 가장 비싼 날 전까지 모든 주식을 매수해서 가장 비싼 날에 전부 판다.
2. 전부 판 다음 날 부터 다시 가장 비싼 날 전가지 모든 주식을 매수해서 가장 비싼 날에 전부 판다.

위 과정을 마지막 날까지 계속 반복하면 된다.

 

재귀

 

난 처음에 재귀로 문제를 해결했다.

 

예를 들어서 다음과 같은 주식 가격이 있다고 하자.

 

3 2 1 10 3 2 9 3 2 8

 

여기서 가장 큰 값은 10이기 때문에 해당 값을 기준으로 다음과 같이 나눌 수 있다.

 

( 3 2 1 10)  ( 3 2 9 3 2 8 )

 

(2 3 1 10)에 해당하는 최대 이득을 구한다. 마지막 날에 가장 비싼 것을 확인할 수 있다.

 

주식 가격이 10이 되기 전까지 모든 주식을 매수해서 10이 될 때 모두 팔면 (30 - 6 = 24) 그 날까지 이득은 24원이다.

 

그 다음 ( 3 2 9 3 2 8 )에 해당하는 최대 이득을 구한다.

 

이 번에는 가장 비싼 날이 마지막 날이 아니기 때문에 해당 값을 기준으로 한 번 더 나눈다.

 

( 3 2 9 ) ( 3 2 8 )

 

나눈 값 모두 가장 비싼 날이 마지막 날이기 때문에 그 전 까지 모두 매수하고 마지막 날에 팔면 된다.

 

이런 식으로 만든 코드는 다음과 같다.

 

<최종 코드>

import sys
sys.setrecursionlimit(int(1e9))
input=sys.stdin.readline
arr=[]
dp=[] # dp[i]=m 의 뜻은 인덱스 i부터 끝까지 가장 큰 값이 m이라는 것을 의미
def get_max(left, right): # left부터 right까지 최대 가격 구함
    # temp_idx=left # 최대값의 인덱스
    if left==right:
        return 0
    # for i in range(left, right+1): # 우선 해당 범위의 최대값과 인덱스 구 함
    #     if arr[i]>arr[temp_idx]:
    #         temp_idx=i
    if dp[left]==left: # 첫 날이 가장 비싸면 그 다음날부터 이득 조사
        return get_max(left+1, right)
    elif dp[left]==right: # 마지막 날이 가장 비싸면 다 사고 마지막 날 팔면 됨
        temp_sum=0
        for i in range(left, right):
            temp_sum+=arr[i]
        return (arr[dp[left]])*(right-left)-temp_sum
    else: # 중간이 가장 비싸면 나눔
        return get_max(left, dp[left])+get_max(dp[left]+1, right)
t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int, input().split())) # 날마다 주가
    dp=[0]*len(arr)
    dp[-1]=len(arr)-1
    temp_idx=dp[-1]
    temp_max=dp[-1]
    for i in range(len(arr)-2, -1, -1):
        if arr[i]>arr[temp_idx]:
            temp_idx=i
        dp[i]=temp_idx
    print(get_max(0, n-1))

 

그리디

다른 사람들의 풀이를 찾아보니 그리디 알고리즘을 적용하면 더욱 쉽게 구할 수 있다는 것을 알아냈다.

 

이득이 최대가 되기 위한 과정은 동일하다.

1. 주식 가격이 가장 비싼 날 전까지 모든 주식을 매수해서 가장 비싼 날에 전부 판다.
2. 전부 판 다음 날 부터 다시 가장 비싼 날 전가지 모든 주식을 매수해서 가장 비싼 날에 전부 판다.

그런데 첫 번째 날부터 시작하는 것이 아닌 마지막 날부터 시작한다면 매우 간단하게 코드를 작성할 수 있다.

 

마지막 날부터 최대값을 갱신해가면서 조사를 한다.

 

만약 최대값보다 해당 날짜의 주식 가격이 작다면 최대값과 해당 날짜의 주식 가격의 차이를 계속 더한다.

 

만약 최대값보다 해당 날짜의 주식 가격이 크다면 최대값을 갱신하면 된다.

 

<최종 코드>

import sys
sys.setrecursionlimit(int(1e9))
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n=int(input())
    arr=list(map(int, input().split()))
    temp_max=0 # 최대값
    temp_sum=0 # 총 매수 주식 가격
    res=0 # 총 이득
    for i in range(n-1 ,-1 ,-1): # 거꾸로 조사
        if arr[i]>temp_max: # 크면 최대값 갱신 
            temp_max=arr[i]
        else: # 작다면 해당 주식을 사고 최대값에 팜
            res+=temp_max-arr[i]
    print(res)

그리디 알고리즘에서는 거꾸로 문제를 해결할 때 훨씬 쉬운 경우가 종종 있는 것 같다.