숫자카드 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다.
27123을 2글자씩 읽어서 숫자로 확인하고 34이상이면 분할한다.
27, 123 으로 분할하고 카드로 표현할 수 있는 형태가 몇개인지 확인한다.
카드로 표현 가능한 개수는 마지막 수를 표현하는 카드가 한자리 수인지, 두자리 수인지로 구분하여 점화식을 구성한다.
D[i] = (D[i-1][0] * 2 )/2 + D[i-1][1] + (D[i-1][0] * 2 )/2
끝자리가 한자리수이면 마지막에 하나더 숫자가 붙어서 두자리 또는 한자리가 될수 있기 때문이다.
끝자리가 두자리수 이면 한자리수로 붙어서 표현이 가능하다.
반응형
'알고리즘 > 정올' 카테고리의 다른 글
| [스크랩] [정올] 문제 해답 (0) | 2017.04.13 |
|---|---|
| [정올][다이나믹] 1520 계단오르기 (0) | 2017.04.13 |
| [정올][최단거리] 1108 페이지 전환 (0) | 2017.04.11 |
| [정올][다이나믹] 1848 극장좌석 (0) | 2017.04.11 |
| [정올][백트래킹] 1027 좋은 수열 (0) | 2016.10.09 |