[BOJ] 백준 1912 연속합 (Swift)

문제

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

1912번: 연속합

풀이

연속된 수들을 선택해서 가장 큰 수를 구하는 문제입니다.

그렇다면 이 두가지로 나뉠 것입니다.

1. 연속해서 자기 자신까지 선택한 경우가 더 큰 경우
2. 자기 자신만 선택한 경우

다이나믹 프로그래밍을 사용해서 풀 수 있습니다.
[2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 수열이 주어졌을 때를 확인해 봅시다.

첫번째 수를 확인해봅시다. 2를 선택하는 것이 가장 큰 합일 것입니다.

두번째 수를 확인해봅시다. 기존의 2와 1을 선택하는 것이 3이므로 가장 큰 합일 것입니다.

세번째 수를 확인해봅시다. 여태까지 선택했던 수에서 자기 자신까지 선택한다면 -1일 것이고,
선택했던 수를 버리고 자기 자신부터 다시 선택한다면 -4이므로 연속해서 선택해주도록 하겠습니다.

네번째 수를 확인해봅시다. -1에서 자기 자신인 3을 더하게 되면 2이므로
여태까지 연속된 수를 선택한 것을 버리고, 자기 자신부터 선택하는 것이 더 크기 때문에 자기 자신부터 선택해주도록 합시다.

마지막 까지 표를 채우게된다면..

이런식으로 채워지겠네요.

이 중 가장 큰 값이 연속된 수를 선택해서 구할 수 있는 가장 큰 합입니다.

정의 : $f(n)$ = n번째 까지 연속된 수들의 합과 자기 자신만 선택한 경우 중 큰 값, $nums$ = 수열
점화식 : $f(n) = max(f(n-1) + nums(i), nums(i))$
초기값 : $f(0) = nums(0)$

소스코드

후기

다이나믹 프로그래밍 문제중에 쉬운 문제인 것 같은데..
다이나믹 프로그래밍은 정말 어렵군요..