(C++) - 백준(BOJ) 20500 : Ezreal 여눈부터 가네 ㅈㅈ

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

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

dp문제였습니다.

📕 풀이방법

📔 입력 및 초기화

10,000,000,007로 나눈 답을 출력해야하므로 MOD 상수를 선언해줍니다. n과 2차원 배열 d를 선언하고 n을 입력받습니다. memoization을 위해 d배열은 -1로 초기화해줍니다.

📔 풀이과정

15는 3과 5의 공배수입니다. 따라서 15의 배수는 3의 배수 특징과 5의 배수 특징을 합친 특징을 가지고 있습니다.

특징은 다음과 같습니다.

 1. 각 자리의 합이 3의 배수

 2. 마지막 자리가 0또는 5인 수

memoization을 이용, dp를 생각해봅니다. 

 

d[len][sum] = len자리인 수면서 나머지가 sum인 수들 중 15의 배수인 경우

 

n자리 수는 1또는 5로만 구성되어 있습니다. len은 0부터 시작해 한 자리씩 1또는 5를 붙여보며 dp함수를 수행합니다.

귀로 수행하므로 n자리까지 한 자리씩 수를 붙였을 때 유효성을 판별합니다. 유효성은 sum이 0이며 이전에 붙였던 1의 자리가 5라면 1, 아니라면 0을 반환함으로써 판별할 수 있습니다.

 

📔 정답출력

dp함수의 수행결과를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int n, d[2000][3];
int dp(int len, int sum, int prev){
    if(len == n) {
        if(!sum && prev == 5) return 1;
        return 0;
    }
    int &ret = d[len][sum];
    if(ret != -1) return ret;
    ret = dp(len + 1, (sum + 1) % 3, 1)%MOD + dp(len + 1, (sum + 5) % 3, 5)%MOD;
    return ret%MOD;
}

int main(){
    memset(d, -1, sizeof(d));
    cin >> n;
    cout << dp(0, 0, 0);
}