[백준] 1912 연속합 (DP) - Python / 자세한 설명 / 실버2

백준 로고

 

 

Contents

---

 

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/1912)

1912번: 연속합

예제 입력과 출력

10 : 수의 개수 
10 -4 3 1 5 6 -35 12 21 -1 : 수의 개수만큼 수를 나열(띄어쓰기로 수를 구분)

수의 나열에 대해, 숫자를 연속으로 더할 때, 나올 수 있는 최댓값을 출력합니다.

 

2. 전체 코드

input() # n은 쓰지 않으니 그냥 input만 받기
s=[*map(int,input().split())] # 수열을 리스트로 저장
d=[s[0]] # dp 리스트
for i in s[1:]: # s의 2번째 원소부터 반복
    d.append(max(d[-1]+i,i)) # 핵심 코드
print(max(d)) # 최대값 출력

3. 일반 풀이 해설

1) 입력 및 dp 리스트 초기화

input() # n은 쓰지 않으니 그냥 input만 받기
s=[*map(int,input().split())] # 수열을 리스트로 저장
d=[s[0]] # dp 리스트

* 코드 설명

수의 개수는 코드에서 필요 없기 때문에 그냥 input()으로 입력만 받고 넘어갑니다. s에 수의 나열을 입력받습니다. dp 리스트인 d에 s[0]만 넣어 초기화합니다. 예제 1번에 대해 위 코드를 수행하고, 출력하면 아래와 같습니다.

(s에서 수열을 입력받는 부분 개념:  [Python] 정수 및 배열 입력 받기 (알고리즘 입력) / sys.stdin.readline(입력 빠르게 하기))

*출력

수의 나열 s와 dp리스트 d 출력

 

2) dp 리스트 채우기

for i in s[1:]: # s의 2번째 원소부터 반복
    d.append(max(d[-1]+i,i)) # 핵심 코드
print(max(d)) # 최대값 출력

* 코드 설명

s의 2번째 원소부터 반복하며, d.append(max(d [-1]+i, i)) 코드를 수행합니다. 이 부분이 핵심입니다. d(dp 리스트)에 최댓값을 갱신하는 코드입니다. 쪼개서 보면, 아래의 2개 중에 최댓값을 d의 마지막에 추가하는 것입니다.

1. d[-1]+i: 현재 원소(i) 전 원소를 포함하는 최댓값 + 현재 원소(i) -> 현재 원소(i)를 포함하는 최댓값의 후보
2. i : 현재 원소

이 의미는 현재 시점(원소 i를 추가할지 말지 결정하려는 시점)에서 d[-1]은 i 전 원소를 포함하는 최댓값입니다. d[-1]에 i를 더한 게, 현재 원소 i 보다 크다면 계속 더해나가는 게 최댓값이 유지가 되는 것이고, d[-1]에 i를 더한 게 i보다 작다면, d[-1]은 음수라는 것이고, 그러면 i부터 새롭게 연속합을 시작해야 합니다. 이 부분이 정말 어렵습니다. 첫 번째 예제에서 첫 번째 원소가 10입니다. 첫번째 원소까지는 10이 유일한 값이자 최댓값입니다. 2번째 원소인 -4를 추가할지 말지 결정할 때, 10-4는 6이고, 현재 원소는 -4기 때문에 일단 추가합니다. 여기서 유의할 점은 d[1]은 10-4=6이 되고 이게 두 번째 원소까지 연속합중에 최댓값이 아니라는 점입니다. 10과 -4 2개만 있을 때 연속 합의 최댓값은 10입니다. 6은 두 번째 원소까지에서 두 번째 원소를 포함하는 연속합중 최댓값입니다. 그래서 마지막에 d[-1]을 출력하는 게 아니고, max(d)를 출력하는 것입니다.

5. 느낀 점

dp는 풀 때마다 어렵습니다. 보통 dp리스트는 해당 인덱스까지의 최댓값을 계속 갱신시켜나가는 경우가 많습니다. 하지만, 이 문제에서의 dp는 해당 인덱스를 포함하는 값 중에 최댓값을 갱신시켜나갑니다. 

 

읽어주셔서 정말 감사합니다.

다음에 더욱 재미있고 유익한 글로 찾아오겠습니다.