[ 백준 1912 ] ( python ) 연속합

 

📚 연속합

 

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

 

 

✍ 접근

• DP를 이용해서 접근하면 된다

 

 

정답 코드 1

import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int,input().split()))
dy = [0]*N
dy[0] = arr[0]
res = -2147000000
for i in range(1,N):
    dy[i] = max(dy[i-1]+arr[i], arr[i])
    if dy[i]> res:
        res = dy[i]
if res < dy[0]:
    print(dy[0])
else:
    print(res)

• 처음 제출했을 때는 틀렸다. -만 있는 경우를 상정하지 못하고 res를 0으로 두어서 틀렸다
• 아무튼 for문을 돌면서 바로 전의 값 + 내 값, 내 값을 비교해서 더 큰 값을 dy에 넣어준다
  • dy값이 res보다 클 경우 res를 dy[i]로 업데이트해준다
• 결과를 출력할때 만약 arr[0]이 가장 큰 경우가 있다면 == res < dy[0]인 경우가 있다면 dy[0]을 출력하고
• 그렇지 않으면 그냥 res를 출력한다.

 

⭐ 배움

• 이대로.. 가보자구!