[백준/BOJ] 20957 농부 비니 - 접근과 풀이 (c++)

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

20957번: 농부 비니

dp는 꾸준히 안하면 무조건 까먹을거 같다. 그중에서도 내가 젤 좋아하는 digit dp문제이다. digit dp를 좋아하는 이유는 직관적으로 규칙이 보이기 때문.

 

---

접근 방법

 

모든 숫자의 합과 곱을 알아야한다. digit dp는 n-1자리의 결과에서 0~9 숫자를 붙일 때 발생하는 규칙을 이용하여 dp 점화식을 세우면 쉽다. 내기준

1. n-1 자리 모든 숫자의 합은 , 0~6의 모든 상태를 알아야한다. 어떤 숫자를 더해도 해당 숫자의 합을 기억해야한다.
2. n-1 자리 모든 숫자의 곱은, 7의 배수인지 아닌지 2가지만 알면 된다.
   - 7의 배수인 경우 어떤 숫자를 곱해도 7의배수이고,
   - 7의 배수가 아닌 경우는 0, 7을 제외한 숫자를 곱하면 7의배수가 아니다.

그러므로 dp배열에 [자릿수], [각 자릿수의 합], [각 자릿수의 곱이 7인가] 를 저장하는 3차원 배열을 이용했다.

 

---

풀이

 

 tag : dp

 

#include<iostream>
#define MOD int(1e9)+7
using namespace std;
int T,N;
int dp[10001][7][2]={0}; //n자리, 합mod7, 7배수인가
void solve(){
  for(int i=2;i<=10000;i++){
    for(int j=0;j<7;j++){
      for(int k=0;k<=9;k++){ // 0 1 2 3 4 5 6 8 9

        //곱이 7배수 아닌수 -> 곱이 7배수인수
        if(k==7 || k==0){
          dp[i][(j+k) % 7][1]+=dp[i-1][j][0];
          dp[i][(j+k) % 7][1]%=MOD;
        }
        else {
          //곱이 7배수 아닌수 -> 곱이7배수 아닌수
          dp[i][(j+k) % 7][0]+=dp[i-1][j][0];
          dp[i][(j+k) % 7][0]%=MOD;
        }

        //곱이 7배수인수 -> 그대로 곱이 7배수
        dp[i][(j+k) % 7][1]+=dp[i-1][j][1];
        dp[i][(j+k) % 7][1]%=MOD;
      }
    }
  }
} 
int main(){
  cin>>T;

  dp[1][0][1]=1; //7
  dp[1][1][0]=2; //1 8
  dp[1][2][0]=2; //2 9
  dp[1][3][0]=1; //3 
  dp[1][4][0]=1; //4
  dp[1][5][0]=1; //5
  dp[1][6][0]=1; //6
  
  solve();

  while(T--){
    cin>>N;
    cout<<dp[N][0][1]<<endl;
  } 
}

 

숫자 0을 처리할 때 주의하자. 곱이 0인 경우도 7의 배수이다.