[백준 1912 파이썬] 연속합 (실버2, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : O

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

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
S = [0]*N
S[-1] = arr[-1]

for idx in range(-2, -N  - 1, -1):
    if S[idx + 1] >= 0:
        S[idx] = arr[idx] + S[idx + 1]
    else:
        S[idx] = arr[idx]

print(max(S))

리뷰

부분 문제를 정의하는 아이디어에서 막혀서 푸는데 시간이 좀 오래 걸렸다.

전체 문제는 수열의 각 인덱스마다, 그 인덱스의 값이 "마지막 값"이 되는 연속합을 리스트에 채우고, max값을 취하는 것이다.

상향식이 for 초기식 조건식 증감식 쓰기 편한데, 이걸 생각못하고 하향식을 떠올려버려서 하향식으로 풀었다. 물론 둘 다 원리는 똑같다.

전체 문제에 해당하는 S 리스트를 먼저 채워야하는데, S[N]은 S[N+1]이 0 이상일 때, arr[N] + S[N+1]이고, 음수일 때는 자기 자신만 취하는게 최대 연속합이므로 S[N] = arr[N]이다.

(참고로 이는 하향식 풀이이고, S[N]은 arr[N]이 "시작 값"인 연속합 중 최대 값을 의미한다.)

좀 더 상세하게 설명을 하자면, S[N]은 arr[N]과 다음 인덱스 값인 arr[N+1]가 시작 값인 최대 연속합 "S[N+1]"을 붙일 수도 있고 안 붙일 수도 있다. 인접해 있는 다음 인덱스의 최대 연속합이 양수이면 arr[N]에 그걸 더해주는 거고, 음수면 오히려 손해니까 자기 자신만인 arr[N]이 S[N]이 되는 것이다.

풀이 요약

1. 구하는 것은 max(S), S는 각 인덱스에 해당하는 arr[idx]가 끝 값인 연속합이다.

2. 먼저 S[0]에 arr[0]을 할당해주고, S[N] = max(arr[N], arr[N] + S[N-1]) 이 점화식이다.

3. idx 0은 채워줬으므로, for를 돌 때 idx 1부터 N-1까지 돌아준다.

4. max(S) 출력

배운 점, 부족했던 점

• 규칙을 찾고 부분 문제를 정의하는 능력을 많이 길러야겠다.

• "부분 문제 정의, 점화식 세우기, 메모이제이션 활용해서 풀기" 3가지 DP 단계를 늘 되새겨야겠다.