[백준 20500번] Ezreal 여눈부터 가네 ㅈㅈ (C++)

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

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

우선 1과 5로만 이루어진 숫자가 15의 배수가 되기 위해서는 마지막 숫자가 5로 끝나야 한다.

마지막 숫자가 5로 끝나면 경우의 수는 3가지이다. 15로 나눴을 때 나머지가 5인경우, 10인 경우, 0인 경우.

 

dp[i][0] 을 i자리수면서 나머지가 0인 경우, dp[i][1]을 i자리수면서 나머지가 5인경우, dp[i][2]를 i자리수면서 나머지가 10인 경우로 생각했다.

저렇게 나누고 4자리수까지 나머지가 0,5,10인 경우를 세 보았는데 다음과 같은 규칙이 보였다.

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];

이전 dp에서 본인을 제외한 나머지 2개를 더한 것이 다음 항이 되었다.

하지만 또 하나 보이는 것이 더해지는 수가 규칙이 또 있어서 점화식을 단순화 할 수 있었다.

자릿수가 홀수인 경우에는 이전항*2-1, 짝수인 경우에는 이전항*2+1 을 만족한다.

 

코드는 다음과 같다.

#include <iostream>
#define prime 1000000007
using namespace std;
int main(){
    int n;
    int dp[1516];
    cin >> n;
    dp[1] = 0;dp[2] = 1;
    for(int i = 3; i < n+1; i++){
        if(i%2==0) dp[i] = (dp[i-1]*2+1)%prime;
        else dp[i] = (dp[i-1]*2-1)%prime;
    }
    cout << dp[n];
}