백준 1912번, 연속합(DP)

- 문제 : https://www.acmicpc.net/problem/1912

 

 

2. 생각해보기

Q1. 이게 왜 DP 문제일까? 
백준의 단계별 문제풀이를 진행하고 있었기에 해당 문제가 DP문제라는 것은 알고 있었다.

내가 생각하는 DP는 점화식이 세워져야 하고, 이전의 결과에 영향을 미치는 구조라고 생각을 했다. 

 

하지만 문제는 이전결과에 영향을 미칠 수도 있고, 아닐수도 있었다. 이부분이 왜 DP지 라는 의문이 들었다. 

 

Q2. DP문제인지는 잘 모르겠고, 생각나는 방식은 브루트포스(완전탐색)으로 풀 수 있나?

=> 문제에서 몇개만 고르라고 딱 정했줬음 좋겠는데, 몇개를 고를지 모르기 때문에, 최소 개수 2만 뽑아도 100,000 * 100,000이다..

문제의 제한시간은 1초이기 때문에 테스트케이스 조차 통과할 수 없다. 

 

도움받기

n번째 숫자를 봤을 때, '내 앞까지의 최선의 연속합에 나를 붙일지, 아니면 그냥 나부터 새로 시작할지'를 결정하면 그게 곧 n번째를 끝으로 하는 최선의 값이 됩니다. 

즉,현재의 최선이 이전 단계의 최선으로부터 결정되기 때문에 DP문제입니다. 

 

 

Q3.점화식 세우기

DP[n] = n번째 숫자를 '반드시 포함'했을 때의 최대 연속합

 

[DP[n]의 입장에서 선택지]

1. "앞에 애들이랑 같이 가기" : 내 앞에 DP[n-1] + 현재데이터 data[n]

2. "혼자 새로 시작하기" : data[n]

결정은, 1번과 2번 중에서 더 큰 값을 고르면 됩니다.

 

[최종점화식]

최종 점화식

 

 

 

3. 결과

https://github.com/moonlight-duck/study-algorithms/pull/58/changes#diff-36b6c6f2b64b7125d324e20dedf7a5cc5edce8f9df6aba003283297c09e8d1d2R1

[민주] 백준 단계별 문제 풀이 - 동적 계획법 1 by min-99 · Pull Request #58 · moonlight-duck/study-algorithms