문제
https://www.acmicpc.net/problem/20500
풀이
- 나머지 연산은 곱과 합이 성립한다.
- N자리 모든 수들의 나머지는 0~14이다.
- number(n)을 어떤 1과 5로만 이루어진 n자리 자릿수 중 하나라고 하자.
- 숫자가 1과 5만 올 수 있다는 것은
- 10^(n) + number(n) (1을 맨 앞에 붙힘)
- 5*10^(n) + number(n) (5을 맨 앞에 붙힘)
- n + 1 자릿수는 이 두개의 수가 올 수 있다는 것이다.
- 나머지 연산은 곱과 합이 성립한다. 따라서 두 수의 나머지는
- 10^(n) % 15 + number(n) % 15
- 5*10^(n) % 15 + number(n) % 15
- 해당 성질에 의해 dp로 문제를 풀 수 있다.
- dp(i,j) = dp(i,j) + dp(i-1,15 + j-10^n%15) + dp(i-1,15 + j-5*10^n%15)
- i: 자릿수,j: 15로 나눈 나머지
'알고리즘문제풀이' 카테고리의 다른 글
| 백준 11834 홀짝 (0) | 2024.05.14 |
|---|---|
| 백준 31741 구간 덮기 (0) | 2024.04.24 |
| 2381 최대거리 (1) | 2024.03.24 |
| 31478 포니 양은 놀고 싶어 (2) | 2024.03.22 |
| 백준 1419 등차수열의 합 (0) | 2024.03.06 |