BOJ 1066 : 에이한수

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

1066번: 에이한수

관찰이 재밌고 어려운 문제이다.

내가 문제 풀 당시에 관찰한 것은
-진짜 A한수에서 A의 자릿수가 비내림차순하게 만드려면 무조건 수열로 분할했을때 모든 수열이 비내림차순이여야 되는것이다.

-A한수는 A+1한수이다. (if A < N) => 찐A한수는 등차수열 그룹의 갯수의 최솟값이 A인 A한수다.

-A>9일때 답은 0이다.

 

이를 이용해 dp로 풀면 

dp[i][j][k][d] = i번째 자릿수 차례, 등차수열 그룹 수가 j, i번째 자릿수가 k, 이전수가 속한 그룹의 등차가 d일때 갯수

라고 정의하고 식 세우면 끝난다.

시복은 O(10^3 * N)이다.

 

자세한건 코드를 참고하자.

 

코드