def solve(X):
X = [*map(int,str(X))]; L = len(X)
for l in range(L):
if X[l] and not X[l]%3:
X[l] -= 1; X[l+1:] = [8]*(L-l-1)
cnt = R = 0
for l in range(L):
x = int(X[l])
for i in range(x):
if i and not i%3:
continue
for r in range(3):
if (R+i+r)%3:
cnt += DP[r][L-l-1]
R += x; R %= 3
cnt %= mod
return cnt+int(R!=0)
def remain():
DP = [[0]*N for i in range(3)]; DP[0][0] = 1
for i in range(1,N):
for r in range(3):
for r0 in range(3):
DP[r][i] += DP[r0][i-1]*(3-2*int(r==r0))
DP[r][i] %= mod
return DP
N = 10**5+1; mod = 20150523
DP = remain()
A,B = map(int,input().split()); A -= 1
print((B-A-solve(B)+solve(A))%mod)다이나믹 프로그래밍으로 해결하였다.
처음에는 박수치는 횟수를 구하려고 시도하였다. 3의 배수의 개수와 3,6,9를 포함한 숫자의 개수에서 3,6,9를 포함한 3의 배수를 빼주는 포함-배제의 원리로 푸려고 했는데, 아이디어가 잘 떠오르지 않았다. 그러다가 굳이 그럴 필요 없이 박수를 안치는 횟수를 구하는게 더 쉽겠다는 생각이 들었다. 즉, 3,6,9를 포함하지 않는 (다시말해, 0,1,2,4,5,7,8로만 이루어진) 3의 배수가 아닌 수의 개수를 구하는 것이다.
알아두어야할 특징 중 하나는, 3으로 나눈 나머지의 특징이다. 10진법 숫자에서 어떤 수를 3으로 나눈 나머지는, 각 자릿수의 합의 나머지와 같다. 즉 1234를 3으로 나눈 나머지는 1+2+3+4로 나눈 나머지와 같다는 것이다.
풀이를 설명하면,
1. 2차원 DP 배열을 만든다. DP[r][i]는 3으로 나눈 나머지가 r인 i번째 자릿수 숫자의 개수를 의미한다. 이때 선행 0이 있는 경우도 포함한다. (예를들어 4자릿수라면 0011도 가능하다)
2. 3,6,9를 제외한 0,1,2,4,5,7,8 중에서 3으로 나눈 나머지가 0인 수는 1개(0), 1인 수는 3개(1,4,7), 2인 수도 3개(2,5,8)이다. 이를 이용하면, DP[r][i] = DP[(r+1)%3][i-1] * 3 + DP[(r+2)%3][i-1] * 3 + DP[r][i-1]이 성립함을 알 수 있다. (위 3으로 나눈 나머지 특징을 이용)
3. i = 10만까지 DP를 구한다.
4. solve(X) 함수에서 X를 리스트로 나열하고, 앞에서부터 3,6,9가 존재할 경우 해당 자릿수에서 1을 빼주고 그 뒤의 숫자는 전부 8로 바꿔준다. (예를들어 314는 100자리 숫자가 3이므로 288로 바뀌고, 1796000은 1000자리 10000자리 숫자가 9이므로 1788888로 바뀐다. 원래수와 바뀐수 사이에는 박수치지 않는 수가 하나도 없다)
5. 맨 앞 자릿수부터 앞자리수가 x인 경우 자릿수가 0~x-1일 때 나머지숫자들을 조합하여 3,6,9의 배수가 아닌 경우의 수를 cnt에 더해준다. 앞자릿수들의 합을 R로 두고, R+x+i = 1 또는 2인 경우에 대해서 DP로 구해준 경우의 수의 개수를 더해주면 된다.
6. A,B가 있는 경우 B까지 박수친 횟수-A-1까지 박수친 횟수를 구하면 되므로, B-(A-1)-(B까지 박수치지 않은 횟수-(A-1)까지 박수치지 않은 횟수) 를 출력한다.
3의 나머지의 성질을 이용하는 재미있는 문제였다.
오늘의 교훈) 숫자의 범위가 크다고 겁먹지 말자