https://www.acmicpc.net/problem/20500
20500번: Ezreal 여눈부터 가네 ㅈㅈ
문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.
www.acmicpc.net
1과 5로만 이루어진 N자리 양의 정수 중에서 15의 배수가 몇 개인지 구하는 문제입니다.
15의 배수는 3의 배수 * 5의 배수입니다.
따라서 3의 배수이고, 5의 배수인 것을 찾으면 됩니다.
dp[N][R]: N자리의 양의 정수를 3으로 나눈 나머지가 R인 경우의 수
따라서 먼저 5의 배수를 만들어 놓고, 3으로 나눈 나머지를 확인하도록 합니다.
우선 N = 1일때는 15의 배수가 없으므로 패스합니다.
N = 2일때는 5의 배수가 15, 55가 있습니다.
15는 3으로 나눈 나머지가 0이므로 dp[2][0]에 해당하고,
55는 3으로 나눈 나머지가 1이므로 dp[2][1]에 해당합니다.
따라서 초기 값은 dp[2][0] = 1, dp[2][1] = 1입니다.
그 다음 N = 3일때는 N = 2일 경우에 1 또는 5를 붙인 경우를 더해주시면 됩니다.
dp[3][0]은 dp[2][1]에서 앞자리에 5를 더한 경우 + dp[2][2]에서 앞자리에 1을 더한 경우
dp[3][1]은 dp[2][0]에서 앞자리에 1을 더한 경우 + dp[2][2]에서 앞자리에 5를 더한 경우
dp[3][2]는 dp[2][0]에서 앞자리에 5를 더한 경우 + dp[2][1]에서 앞자리에 1을 더한 경우
따라서 점화식은 위와같이
dp[i][0] = dp[i - 1][1] + dp[i - 1][2]
dp[i][1] = dp[i - 1][0] + dp[i - 1][2]
dp[i][2] = dp[i - 1][0] + dp[i - 1][1]
이렇게 됩니다.
결과로는 MOD를 한 값을 출력해야 하므로 더하면서 MOD값을 넣어주도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>
#define MAX 1516
#define MOD 1000000007
using namespace std;
int dp[MAX][3];
int N;
void init() {
dp[2][0] = 1;
dp[2][1] = 1;
for (int i = 3; i < MAX; i++) {
dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
}
}
void input() {
cin >> N;
cout << dp[N][0] << '\n';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 14238 출근 기록 (0) | 2022.02.04 |
|---|---|
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
| boj 1135 뉴스 전하기 (0) | 2021.11.15 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
| boj 1648 격자판 채우기 (0) | 2021.06.22 |