[Silver II] 수익 - 4097 (dp)

[Silver II] 수익 - 4097

문제 링크

성능 요약

메모리: 41372 KB, 시간: 1080 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.

어느 날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.

오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.

• 1일: -3
• 2일: 4
• 3일: 9
• 4일: -2
• 5일: -5
• 6일: 8

이때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안 된다.

import sys
input = sys.stdin.readline
while True:
  n = int(input())
  if n == 0:
    break
  
  elif n == 1:
    num = int(input())
    print(num)
  else:
    dp = []
    for i in range(n):
      num = int(input())
      dp.append(num)
    for i in range(1,n):
      dp[i] = max(dp[i], dp[i]+dp[i-1])
    print(max(dp))

너무나 일반적인 점화식의 DP라 규칙을 찾아 금방 풀 수 있었다.

연속적인 가장 큰 부분을 찾으면 되기 때문에, 해당 인덱스의 값과 해당인덱스 이전과 현재를 더한 값과 비교하여 최댓값을 계속 가져오면된다. 여기서 dp[-1]을 출력해도 될 줄 알았는데 그냥 시간초과가 나 버려서 이유가 뭔지 조금 더 고민 중이다.