[Python] 백준 4097. 수익

문제

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

연종이는 창업했다. 오늘은 창업한지 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이 주어진다.

출력

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

---

풀이

여러 개의 테스트 케이스로 이뤄져있기 때문에, While문으로 0이 들어오면 종료하게 if문을 넣어주고 외에는 이제 값이 들어왔을때 가장 많은 수익을 올린 구간을 출력하도록 max를 사용했다.

import sys
input = sys.stdin.readline

while True:
    n = int(input().strip())

    if n == 0:
        break
    else:
        result = [0] * n
        for i in range(n):
            if i == 0:
                result[i] = int(input().strip())
            else:
                a = int(input().strip())
                result[i] = max(a, result[i-1]+a)
        print(max(result))

 

이 코드를 칠 때, 가장 신경썼던 부분은... Dp를 이용해서 해결했는데... result가 dp라고 생각하면 된다. 

예제로...

6
-3
4
9
-2
-5
8

 

이걸 바탕으로 해보면, 총 6일의 수익이 작성되어있고 (-3 ~ 8) 어떤 구간부터 어떤 구간까지의 합이 최대인지 result(dp)에 저장해서 max값을 출력하면 되는 거다. 

 

1. -3 을 일단 result[0]에 넣고

2. 4가 들어오면, result[0]+4 한 값이 큰지 아니면 4만 들어온 게 큰지 확인해서 둘 중에 큰 값을 result에 저장한다.

 

... 이걸 반복하면 result[i-1]+result[i]와 result[i]를 비교해서 큰 값을 저장하게 된다. 이게 즉 무슨 소리냐면, 그 dp에 저장된 값이 최댓값이라 그 이후에 i에서 i-1 합과 지금의 값(i)을 비교해서 둘 중에 큰 값을 저장하는 거다.

 

그렇게 모든 구간의 최대값을 result라는 dp에 저장하게 되면, max(result)를 이용해서 result 배열에 있는 가장 큰 값, 즉 가장 많은 수익을 올린 구간을 출력할 수 있게 된다.

 

시간복잡도

테스트케이스 경우를 잘 모르겠지만... 일단 테스트 케이스 내부에 있는 for문은 O(n)인 걸 알 수 있다.