BOJ 1066 : 에이한수
2021. 8. 3. 22:31ㆍPS/DP
https://www.acmicpc.net/problem/1066
1066번: 에이한수
첫째 줄에 N자리이면서 진짜A한수의 개수를 1,000,000,007로 나눈 나머지를 출력한다.
www.acmicpc.net
관찰이 재밌고 어려운 문제이다.
내가 문제 풀 당시에 관찰한 것은
-진짜 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)이다.
자세한건 코드를 참고하자.
'PS > DP' 카테고리의 다른 글
BOJ 17428 : K번째 괄호 문자열 (0) | 2021.08.14 |
---|---|
BOJ 6171 : 땅따먹기 (1) | 2021.08.08 |
BOJ 22348 : 헬기 착륙장 (0) | 2021.07.31 |
BOJ 1056 : 수 (2) | 2021.07.29 |
BOJ 20984 : Growing Vegetables is Fun 4 (0) | 2021.05.11 |