백준 20957 농부 비니

문제

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

20957번: 농부 비니

 

풀이

모든 자릿수의 곱이 7의 배수인건

0또는7이 수에 하나이상 있으면 된다. (0도 7의 배수이다.)

모든 자릿수의 합이 7의 배수인건 DP로 풀어야한다.

최대 10000자릿수이므로 브루트포싱은 무리가 있고 X%7 + Y%7 = (X%7 + Y) % 7이 성립하므로 우리가 관심있는건 이전의 나머지(0~6)과 현재수(0~9)의 나머지(0~6)이 된다.

 

 

DP테이블을 작성해보자.

DP[n][r]: n자릿수일때 자릿수의 합의 나머지가 r인 경우의 수

이 DP테이블의 점화식은 이렇게 채울 수 있다.

for pr in [0:6]:
	// pr: 이전 자릿수의 나머지
    for k in [0:9]: 
    	// k: 현재 자릿수에 넣어줄 수
        r = (k + pr) % 7
        dp[n][r] = (dp[n][r] + dp[n-1][pr]) % 1000000007

 

하지만, 이 DP의 값을 사용해 곱조건을 만족시키는 수를 찾기엔 고통스러운 케이스처리가 필요하다.

따라서 DP테이블을 수정할 필요가 있다.

DP[n[[r][s]: n자릿수일때 자릿수의 합의 나머지가 r이고 s가 0이라면 자릿수의 곱이 7의배수가 아니고, s가 1이라면 자릿수의 곱이 7의 배수이다.

현재 넣어줄 수가 0또는 7이라면, DP[n][0][1] = 점화식 형태일 것이고,

아니라면 DP[n][r][1] = (이전에 0또는 7을 넣어준 경우(7의배수를 만족하는 경우)에 관한 점화식)

DP[n][r][0] = (7의 배수를 만족하지 않는 경우에 대한 점화식) 형태일 것이다.

for pr in [0:6]:
	// pr: 이전 자릿수의 나머지
    for k in [0:9]: 
    	// k: 현재 자릿수에 넣어줄 수
        r = (k + pr) % 7
        if (k == 0 || k == 7): // 현재 넣어줄 수로 이전 상태와 관련없이 7의 배수를 만들 수 있다.
        	dp[n][r][1] = (dp[n][r][1] + dp[n-1][pr][0] + dp[n-1][pr][1]) % 1000000007	
        else:
        	//만약 이전에 7의 배수를 만족한다면, 어떤 수를 넣어도 7의 배수이다.
        	dp[n][r][0] = (dp[n][r][0] + dp[n-1][pr][0]) % 1000000007
            //만약 이전에 7의 배수를 만족하지 않는다면, 어떤 수를 넣어도 7의 배수가 아니다.
            dp[n][r][1] = (dp[n][r][1] + dp[n-1][pr][1]) % 1000000007

 

하지만 이 DP도 그대로 쓰기엔 무리가 있다.

 0으로 시작하지 않는 양의 정수에 대해서만 계산해야하기 때문이다.

이럴땐, 맨앞자리수 X(1~9)를 직접 지정해주면 된다.

Y는 (X + Y) % 7 = 0를 만족하는 수(0~6)라고 하자.

X가 7이 아니라면

수들의 합의 나머지가 Y여야하고, 0또는 7이 포함(s=1)돼야한다.

앞자리만 수를 지정했으므로 N-1길이를 참조한다.

따라서 dp{N-1][Y][1]값을 참조한다.

X가 7이라면

Y는 0일 것이다.

0또는 7이 포함돼야하거나 포함하지 않아도 된다.

따라서 dp[N-1][0][1] + dp[N-1][0][0]값을 참조한다.

 

코드

M = 10000
dp = [[[0, 0] for _ in range(7)] for _ in range(M)]
R = 10 ** 9 + 7
for i in range(10):
    if i == 7 or i == 0:
        dp[0][i % 7][1] += 1
    else:
        dp[0][i % 7][0] += 1
for i in range(1, M):
    for j in range(7):
        for k in range(10):
            r = (j + k) % 7
            if k == 7 or k == 0:
                dp[i][r][1] = (dp[i][r][1] + dp[i - 1][j][0] + dp[i - 1][j][1]) % R
            else:
                dp[i][r][0] = (dp[i][r][0] + dp[i - 1][j][0]) % R
                dp[i][r][1] = (dp[i][r][1] + dp[i - 1][j][1]) % R
for _ in range(int(input())):
    N = int(input())
    if N <= 2:
        print([0, 1, 2][N])
        continue
    ans = 0
    for i in range(1, 7):
        x = 7 - i
        ans = (dp[N - 2][x][1] + ans) % R
    ans = (ans + sum(dp[N - 2][0])) % R
    for i in range(8, 10):
        x = 14 - i
        ans = (dp[N - 2][x][1] + ans) % R
    print(ans)