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

문제링크 : https://www.acmicpc.net/problem/20500

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

const int MOD = 1000000007;
int N, dp[1516][3];

int func(int n, int sum, int cur)
{
    if(n==N)
    {
        return ((!sum  && cur == 5)?1:0); //3의 배수이고 끝자리가 5라면 카운팅 (15의 배수)
    }

    if(dp[n][sum]) return dp[n][sum];
    dp[n][sum] = func(n+1, (sum+1)%3, 1) % MOD + func(n+1, (sum+5)%3, 5) % MOD; //자릿수 증가, 자릿수합 체크, 다음 끝자리
    return dp[n][sum]%MOD;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    
    cout << func(0, 0, 0);

    return 0;
}

 

먼저 15의 배수의 모든 자리의 수자 합이 3의 배수인 것을 알아야 한다.

나는 이를 몰랐고, 검색을 통해 따로 알 수 있었다.

 

그리고 올 수 있는 숫자가 1 or 5이기 때문에 끝자리는 항상 5인 것을 알 수 있다. (15의 배수)

이를 토대로 재귀 탐색을 하게 된다.

재귀에서 넘기는 값은 총 3개로 자릿수, 자릿수합, 끝자리 숫자이다.

 

자릿수는 매번 1씩 증가하므로 n+1을 통해 매 탐색마다 1씩 증가시켜준다.

그리고 다음에 올 수 있는 숫자가 2가지 이므로 각 2가지에 대해 재귀를 진행해야 한다.

 

먼저 1이 오는 경우다.

1이 온 경우 자릿수합을 저장하는 변수 sum에 1을 저장해주고 3으로 나누어 떨어진 나머지 값을 넘겨준다.

추가로 끝자리가 1이라는 의미이므로 끝자리에 해당하는 cur을 1로 넘겨준다.

 

다음으로 5가 오는 경우다.

기본적은 흐름은 1이 오는 경우와 같으며 1을 더해주고 넘긴 부분을 5로 바꿔주면 된다.

(sum+5)%3, 5

 

이를 자릿수가 입력받은 N에 도달할 때까지 반복하여 N까지 도달했다면 만들어진 값이 문제의 조건을 통과하는지 최종확인해야 한다.

3으로 나누어 떨어진 나머지가 0이라면  3의 배수라는 것이고, 끝자리 cur == 5인지도 추가로 확인해준다.

위 2가지 조건을 무사히 통과하면 현재 만들어진 값이 문제없다는 것이기에 1을 반환하여 카운팅하게 된다.

 

그리고 해당 문제에 위 과정을 걸쳐 저장된 값을 10000000007로 나눈 나머지를 출력하도록 했으므로 이를 잊으면 안된다.