[정올][다이나믹] 1407 숫자카드

숫자카드 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다.

27123을 2글자씩 읽어서 숫자로 확인하고 34이상이면 분할한다.

27, 123 으로 분할하고 카드로 표현할 수 있는 형태가 몇개인지 확인한다.

카드로 표현 가능한 개수는 마지막 수를 표현하는 카드가 한자리 수인지, 두자리 수인지로 구분하여 점화식을 구성한다.

D[i] = (D[i-1][0] * 2 )/2 + D[i-1][1] + (D[i-1][0] * 2 )/2

끝자리가 한자리수이면 마지막에 하나더 숫자가 붙어서 두자리 또는 한자리가 될수 있기 때문이다.

끝자리가 두자리수 이면 한자리수로 붙어서 표현이 가능하다.

개발자로 살아남기