백준 1912번 (동적 프로그래밍, 연속합)

일단 동적프로그래밍을 사용하지 않고 반복문으로 짜보았다.

i는 더할 문자열의 길이, j는 더할 문자열의 첫 인덱스이다.

예를 들어 N이 10이면

i = 1, j = 0 ~ 9

i = 2, j = 0 ~ 8

~

i = 10, j = 0 이다.

 

L[0], L[1], ~, L[9]

L[0]+L[1], L[1]+L[2], ~, L[8]+L[9]

~

L[0]+L[1]+ ~ + L[9]

를 모두 비교해서 가장 큰 값을 찾는다.

 

결과는... 당연히 시간초과였다.

 

이 문제는 연속합이므로 사용할 수 있는 아주 좋은 풀이법이 있었다.

 

예를 들어 입력받은 수가

10 -6 3 -5 2 4 1 이면

 

먼저 10과 -6을 더한 4와 -6을 비교한다. 4가 더 크므로 -6을 4로 교체한다.

10 4 3 -5 2 4 1

 

4와 3을 더한 7과 3을 비교한다. 7이 더 크므로 3을 7으로 교체한다.

10 4 7 -5 2 4 1

(만약 더한 값이 3이고 더하지 않은 값이 7이었다면 7을 그대로 두게된다.)

 

이런 식으로 계속 진행하면 답이 나오게 된다.

위에 3번 째 수를 7로 교체 한다는 말은 곧 1,2,3번째 수를 연속합 한 것중에서 3번째 수를 무조건 포함한다면 가장 큰 수가 7이라는 뜻이다.

 

이 알고리즘이 정말 맞는건지 의문이 생겼다.

예를들어 -8 4 12 -6 이 있다.

그냥 눈으로 풀어도 4와 12를 더한 16이 정답이다. 여기에 이 알고리즘을 사용해보자.

-4와 4를 비교한다. 4가 더 크므로 그대로 둔다. -4 4 12 -6

16과 12를 비교한다. 16으로 교체해준다. -4 4 16 -6

10과 -6을 비교한다. 10으로 교체해준다. -4 4 16 10

이 중 가장 큰 수를 찾아본다. 16이다. 정답이다.

 

이 문제가 연속합 중 가장 큰 값을 구하는 문제이기 때문에 가능한 알고리즘이었다.

 

알고리즘에서 큰 목표를 구하기 위해서 작은 목표부터 조금씩 늘려나가는 방식이 참 효율적이고 멋지다는 생각이 들었다.