[BOJ 20957, C++] 농부 비니

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

20957번: 농부 비니

 

풀이

일단 숫자의 합이 7의 배수가 되는 경우의 규칙성은 찾기가 힘들어 보이고, 숫자의 곱이 7의 배수가 되는 경우에는 곱할 때 0 또는 7이 있으면 됩니다. 7이 들어가는 것은 당연하니 생략하고, 0이 들어가는 것은 보통 배수라고 하면 1이상의 자연수부터 생각하는데 문제 힌트에서 70의 경우에도 조건을 만족한다고 했으니까 0도 가능하게 됩니다.

 

모듈러 연산이 있으니까 우선 DP를 생각해볼 수 있습니다. 게다가 문제 내용이 해당 조건을 만족하는 수를 구하는 것이므로 더더욱 DP일 확률이 높습니다.

메모리는 n = 10000일 때와 곱하기를 생각하면 dp[10001][2]를 생각해볼 수 있습니다. [2]의 경우에는 7이나 0이 들어갈 경우엔 1, 아니면 0으로 표시하는 것입니다.

그리고 더하기의 경우를 생각해야 하는데, 0부터 9까지 모든 수를 붙여보면서 확인하므로 합동식을 이용하여 숫자를 더하면서 계속 7로 나눠주면 되기 때문에 dp[10001][2][7]이 될 수 있습니다.

 

저러고 이제 bottom-up을 해주면 됩니다.

4중 for문을 사용하여 i = 숫자의 길이, j = 7과 0이 들어갔는지, k = 이전에 선택한 숫자, l = 현재 선택한 숫자로 만들어주면 됩니다.

 

top-down 코드도 봤는데 scanf와 printf까지 사용해야 돌아갑니다. 이것도 윗 방식과 비슷한데, 곱하기도 합동식을 사용하여 dp[10001][8][8]로 해주면 됩니다.

 

 

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
const int N = 1e4 + 1, MOD = 1e9 + 7;
int t, n;
ll dp[N][2][7];
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(dp, 0, sizeof(dp));
    dp[1][1][0] = 1;
    for (int i = 1; i < 10; i++) {
        if (i != 7) dp[1][0][i % 7]++;
    }
 
    for (int i = 1; i < N - 1; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 7; k++) {
                for (int l = 0; l < 10; l++) {
                    if (l == 0 || l == 7) dp[i + 1][1][k] = (dp[i + 1][1][k] + dp[i][j][k]) % MOD;
                    else dp[i + 1][j][(k + l) % 7] = (dp[i + 1][j][(k + l) % 7] + dp[i][j][k]) % MOD;
                }}}}
 
    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n][1][0] << '\n';
    }
}