[BOJ/백준][Gold5] 20500 : Ezreal 여눈부터 가네 ㅈㅈ (C++)

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

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

 

 

[난이도] Gold5
[유형] DP

[풀이]
3의 배수의 모든 자릿수의 합을 3으로 나눈 나머지는 0 이라는 성질을 알고 있어야 풀 수 있는 문제입니다.
15의 배수의 1의 자리수는 0또는 5인데 문제의 조건에 의해 1의 자리에는 5밖에 올수밖에 없습니다.
이를 만족하면서 위의 3의 배수의 성질을 만족하는 모든 수를 찾아주면 됩니다.

dp[i][j] : 자리수가 i이면서 각 자리수의 합을 3으로 나눈 나머지가 j인 수들의 개수

위와 같이 정의해주면 아래와 같은 점화식이 나옵니다.

dp[i][0]=(dp[i-1][1]+dp[i-1][2]); // (1+5)%3==0, (2+1)%3==0
dp[i][1]=(dp[i-1][2]+dp[i-1][0]); // (2+5)%3==1, (0+1)%3==1
dp[i][2]=(dp[i-1][1]+dp[i-1][0]); // (0+5)%3==2, (1+1)%3=002

최종적으로 dp[N][0]을 출력해주면 됩니다.

 

 

#include <cstdio>
int N,mod=1e9+7,dp[1600][3];
int main(){
    scanf("%d",&N);
    dp[2][0]=dp[2][1]=1;
    for(int i=3;i<=N;i++){
        dp[i][0]=(dp[i-1][1]+dp[i-1][2])%mod;
        dp[i][1]=(dp[i-1][2]+dp[i-1][0])%mod;
        dp[i][2]=(dp[i-1][1]+dp[i-1][0])%mod;
    }
    printf("%d",dp[N][0]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/20500.cpp