[백준] 1912번 연속합(feat. 다이나믹 프로그래밍)

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

문제 분석

• 첫 번째 단계 (문제 요약 및 조건 파악하기)

n개의 정수로 이루어진 임의의 수열이 주어진다.
이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이다.

ex) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어지면, 여기서 정답은 12 + 21 인 33이 정답이 된다.

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

 

• 두 번째 단계 (문제 핵심 파악하기)

문제를 이해 해보면, 
10, -4, 3, -20, 30이 있다면,
배열 list_a에 일단 [0]을 담아 놓고,
0 + 10과 10 을 비교하여 더 큰 값을 list_a에 담는다. 그러면 list_a[0, 10]이 될 것이다.
이번에는 10 + (-4)와 -4를 비교하여 더 큰 값을 list_a에 넣는다. list_a[0, 10, 6]이 될 것이다.
이번에는 6 + 3과 3을 비교한다. 더 큰 값을 list_a에 넣는다. list_a[0, 10, 6, 9]가 될 것이다.
이번에는 9 + (-20)과 -20를 비교한다. 더 큰 값을 list_a에 넣으면, list_a[0, 10, 6, 9, -11]이 될 것이다.
이번에는 30 + (-11)과 30을 비교한다. 더 큰 값을 list_a에 넣으면, list_a[0, 10, 6, 9, -11, 30]이 될 것이다.
입력받은 배열을 다 돌았다.
그러몋다면, list_a에서 가장 큰 값이 입력받은 배열에 있는 숫자를 연속적으로 선택해서을 통해서 만들 수 있는 가장 큰 수가 될 것이다.

이것을 코드로 구현하면 될 것이다.

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

ex) 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어지면,
여기서 정답은 12 + 21이 정답이 된다.

i) dp_table을 만들고, 0번째 인덱스에는 입력받은 테이블의 0번쨰 인덱스 값을 넣어놓는다.
그리고 dp_table의 i 번째 값과 입력받은 테이블의 i + 1 번째인덱스의 값을 합한 값과, 입력받은 숫자의 i + 1번째 값을 비교하여
더 큰 숫자를 dp_table i + 1에 넣어준다.
그리고나서 dp_table에서 가장 큰 값을 출력한다.

구현 해보자.
'''

 

코드 작성

import sys


minus_INF = int(-1e9)

# n 입력받기
n = int(sys.stdin.readline().rstrip())
# 수열 입력받기
table = list(map(int, sys.stdin.readline().rstrip().split()))
# 인덱스 맞춰주기 위해 table에 minus_INF을 append
table.append(minus_INF)

# dp_table[i] = max(dp_table[i - 1] + table[i], table[i]) 값을 비교해서 저장하기 위해 dp_table 선언 밎 초기화
dp_table = [0] * (n + 1)
dp_table[0] = table[0]

for i in range(1, n + 1):
    dp_table[i] = max(dp_table[i - 1] + table[i], table[i])

print(max(dp_table))

 

'''
대부분의 테스트케이스에는 맞으나, 반례를 발견함.

5
-1 -2 -3 -4 -5

디버깅 해본 결과,
인덱스를 맞춰주기 위해 table에 0을 append해준 것이 문제임을 파악함.

만약, 테이블의 모든 값이 음수인 경우, 마지막에 append한 0이 최대값이 되어, 0이 출력되는 문제였다.
따라서, 인덱스를 맞춰주기 위해, 의미없는 값을 넣어주기 위해선, 입력값의 범위를 고려하여, 그 입력값의 하한 범위를 벗어나는 값을 넣어줘야,
구현한 로직과 max가 정상적으로 작동. 그래서 minus_INF 라는 변수를 선언하고, int(-1e9)로 초기화 해줌.
'''

처음 코드를 작성할 때, for문의 인덱스를 맞춰 주기 위하여,
table에 0을 append해주었었는데, 이것이 문제가 되었었다.

만약, 테이블의 모든 값이 음수인 경우, 마지막에 append한 0이 최대값이 되어 0이 출력되는 문제였다.

따라서, 인덱스를 맞춰주기 위해, 의미없는 값을 넣어주기 위해선, 입력 값의 범위를 고려하여, 그 입력값의 하한 범위(max연산을 진행하므로)를 벗어나는 값을  넣어줘야한다.
그래야 구현한 로직과 max가 정상적으로 동작한다.
그래서 minus_INF라는 변수를 선언하고, int(-1e9)로 초기화를 해주었고, 0대신 이 값을 append 하여 문제를 해결했다.

다른 문제를 풀 때도, 주의해야 한다.

쉬워 보이는 문제라고 방심하지 말자.