[백준] 1912번: 연속합

링크: www.acmicpc.net/problem/1912

1912번: 연속합

연속합

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

---

문제접근

이번문제는 동적 계획법(Dynamic programming) 통해 문제를 풀어야한다.

 

입력으로 들어온 정수의 배열을 for문을 통해서 반복하는데, 지금까지 더해온 값과 다음값의 합을 구하고, 그냥 다음 값을 비교해서 dp array에 추가하는 방식으로 간단하게는 짤 수 있지만,,,, 나는 솔직히 이해하는데에 시간이 걸렸다...

 

즉 연속합의 값을 저장하는 sum 리스트를 선언하고 입력으로 받은 배열을 data라하면 점화식은 간단하게

max(sum[idx] + data[idx+1], data[idx+1])가 될 것이다.

해당 식의 의미는 지금까지 더해온 값 sum[idx]에서 다음으로 더할 값 data[idx+1]의 합한 값과 그냥 다음 숫자부터 다시 연속합을 구하는 수(data[idx+1])을 비교해서 연속합을 구하는 과정인 것이다.

---

코드

"""
백준 알고리즘 1912번: 연속합
https://www.acmicpc.net/problem/1912

DP로 푸는 문제
점화식은 max(sum[i]+data[i], data[i+1])
해당 식의 의미는
지금까지 더해온 값 sum, 주어진 리스트 data에서
현재까지 더해온 값 sum[i]에서 data[i+1](다음 숫자)를 더한게 큰지
아니면 그냥 data[i+1](연속해서 더해 오던 것을 초기화 하는 것)한게
큰지 비교해서 더 큰 수를 추가하는 것
"""
import sys

def calc(n, data):
    sum = [data[0]]
    for i in range(n-1):
        # 다음(i+1) 숫자와의 합이 큰지, 그냥 다시 연속해서 합을 구하는게 큰지 비교
        sum.append(max(sum[i]+data[i+1], data[i+1]))
    return max(sum)

def main():
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().split()
    data = [int(i) for i in data]
    print(calc(n,data))

if __name__ == "__main__":
    main()

주석을 잘 읽어본다면 문제에 해석은 어렵지 않다고 생각한다.