[python/파이썬] 백준 4097 수익

[문제 출처] 

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

4097번: 수익

 

[소스 코드1]

dp[n]에 저장되는 값은 n일까지 돈을 벌었을 때 가장 수익이 높은 구간의 값이다.

따라서 dp[n]은 dp[n-1] + arr[n]  값과 arr[n] 값 중에 더 큰 값을 저장한다.

n번째도 이어가는 것이 더 수익이 높은지 아니면 n번째부터 다시 시작하는 게 더 높은지 비교한다.

import sys
input = sys.stdin.readline

while True:
    n = int(input())
    
    if n==0:
        break
    arr = []
    for _ in range(n):
        arr.append(int(input()))
    dp = [0 for _ in range(n)]
    
    dp[0] = arr[0]
    
    for i in range(1,n):
        dp[i] = max(dp[i-1] + arr[i], arr[i])
    print(max(dp))

 

[소스 코드2]

 

거의 같은 코드이지만 arr 리스트랑 dp리스트 이렇게 2개를 쓰지 않고 한 개의 리스트로 구현한 코드이다.

좀 더 간단한 코드이다.

import sys
input = sys.stdin.readline

while True:
    n = int(input()) 
    if n==0:
        break

    arr = []
    for _ in range(n):
        arr.append(int(input()))
    
    
    for i in range(1,n):
        arr[i] = max(arr[i-1] + arr[i], arr[i])

    print(max(arr))