동적계획법. [11057]

[1. 문제 설명]

[2. 풀이 접근]

완전 탐색 후 메모이제이션 으로 최적화 하는 방법과

반복적 동적계획법을 이용한 풀이 둘다 가능하다.

두 풀이에서 공통 핵심은 현재 선택 할 수 있는 숫자는 바로 이전 숫자에만 영향을 받는다는 것이다.

여기서는 반복적 동적계획법 풀이를 정리한다.

반복적 동적계획법에서는 부분 문제간의 의존 관계를 고려하여 계산 할 순서(방향)을 고민해야 한다.

이 문제에서는 앞자리에서 뒷자리로 이동하는 것이아니라

뒷자리에서 앞자리로 이동하면서 계산을 해나가야 한다.

그 이유는 바로 현재 선택 할 수 있는 숫자는 바로 이전 숫자에만 영향을 받기 때문이다.

아래 그림에서 바로 앞자리가 9 이면 뒷자리는 9

바로 앞자리가 8이면 8~9 로 그 올 수 있는 값을 바로 정할 수 있다.

=> 기저 사례를 바로 계산 할 수 있다.

다음은 바로 앞자리가 8일때, 두번째 자리에 올 수 있는 경우를 따져보는 것이다.

바로 앞자리가 8이면, 두번째 자리에 올 수 있는 숫자는 8~9 이다.

그런데 두번째 자리에 8 또는 9 가 오는 경우는 바로 앞에서 계산 하였으므로, 이 값을 활용 할 수 있다.

이전에 계산 한 값들을 모두 이번에 계산 할 값에 더하는 것이다.

[3. 코드]

[3. 코드 - 재귀적 동적계획법]

test_kernelv2