[BOJ] 연속합_1912

이 문제는 쉽게 해결될 줄 알았는데 풀이를 보고도 어렵다고 느꼈다.

결론부터 보자면, dp.append(max(dp[i-1] + data[i], data[i])) 이 부분은 다시 봐도 정확히 이해가 되지 않는다.

저 한줄의 코드가 각 항 마다, 이전까지 더한 값이 더 크냐 or 현재 값이 더 크냐를 의미한다.

하지만 저것이 어떻게 모든 경우의 수를 고려해준 것일까??

 

해당 코드를 그림으로 나타낸 것이다.

dp[i] = max(dp[i-1]+data[i], data[i])에서 dp[i-1]은 이전까지 구한 값 중 최대의 값을 만들어낸 값이다.

그 전까지 더했을 때, 더 이득이 되는 것만 값을 더했기 때문이다.

그러한 값과 현재의 값을 더했을때와 더하지 않았을 떄의 값을 비교해서 최대값을 구하는 것이다.