boj 20500 Ezreal 여눈부터 가네 ㅈㅈ

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

20500번: Ezreal 여눈부터 가네 ㅈㅈ

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값을 넣어주도록 합니다.

 

 

#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;
}