[C++] 백준 1912번 연속합

DP 문제.

수를 연속해서 선택하는데, 어떤 경우에 해당하는 번째의 수가 최대값을 가지게 되는지 구하는 문제이다.

 

문제에 접근한 방식

 

문제를 읽어보고, DP Bottom Up 방식으로 접근을 시도했다.

• 값을 더했을 때 계속 양수인 경우, 계속해서 더해주면 그게 구할 수 있는 가장 큰 합이 된다.
• 값을 더했을 때 음수가 나오는 경우, 그 값을 더하지 않는 것이 더 큰 값이므로 더이상 더해주지 않고 새로 시작한다.

따라서 점화식은 최대값이 An이고, 현재 수가 Bn을 나타낼 때

An = max( A(n-1) + Bn, Bn)이 된다.

이렇게 두 개를 고려하고 문제를 접근하면 된다.

자세하게 고려하고 풀지는 않았는데, 지금 보니 왜 저렇게 생각했는지 풀었으면 더 좋았을 것 같다.

 

문제풀이

 

사용한 STL과 변수

최대값을 갱신시켜 주기위해 <algorithm> STL을 사용해서 max 메서드를 사용했다.

n개를 입력받기 위해 n을 입력받고 각 수를 입력받는 arr배열,

그리고 각 번째마다의 최대값을 저장하는 dp배열

결과값인 result 변수가 있다.

 

n을 입력받고 n개의 정수를 입력받는다.

그리고 첫번째의 최대값은 첫번째와 같으므로 dp[1]을 arr[1]로 초기화한다.

반복문을 i=2부터 돌면서 위에 적은 점화식An = max( A(n-1) + Bn, Bn)으로 dp배열을 업데이트하고

결과값은 삼항연산자로 업데이트 시킨다.

마지막에 결과값을 출력한다.

DP인게 운좋게 빨리 보인건지, 요즘 DP문제를 많이 풀어서 바로 보인건지 모르겠지만 바로 맞췄다.

중간에 틀렸습니다는 원래 최초 코드는 result를 -1001로 초기화하고

마지막에 for반복문을 1부터 n까지 또 돌려서 갱신했었는데,

시간을 줄이려고 아예 dp값을 갱신할때 같이 result를 받아왔었다. dp[1]이 최대값인 경우를 고려안했어서 한번 틀렸다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.