[2023 Seoul Regional J, BOJ 30861] Special Numbers

리유나입니다. ICPC에서 제가 풀었던 문제의 풀이를 조금 더 자세히 적어보려고 합니다. 대략적인 풀이의 스케치는 이 글의 아랫부분에 있습니다.

 

수학문제와 dp문제의 경계 어딘가쯤에 있는 Digit DP라는 스타일의 문제이고, 사실 저는 수학이라고 생각하고 접근했다가 '에이 수학 아니잖아... 하지만 풀이는 나왔으니 뭐 풀어야지'하고 풀었습니다.(Digit DP라는 말이 있는 걸 대회 후에 처음 알았습니다.)한국 리저널에는 잘 안나오던 스타일의 문제인 듯한데, 제게는 찐수학만큼은 아니지만 상당히 강한 유형이었기 때문에 그리 어렵지 않게 풀었습니다....였으면 얼마나 좋았을까요? 예외처리 하느라 고생하면서 조금 어렵게 풀었습니다.

 

문제를 해석하면, L부터 R까지의 자연수 중에서 모든 자릿수를 곱했을 때 k로 나누어떨어지는 수가 몇개인가?를 묻는 간단한 문제입니다. 이것만 보면 별로 안 어려워보이지만, L과 R의 범위는 10^20이며 k의 범위는 10^17입니다. 그렇다면 우리는 망한 걸까요? 일단 k를 인수분해하기 위해서 폴라드 로부터 때려박아야 할까요?

 

사실 k를 인수분해할 필요도 없다는 것을 어렵지 않게 알 수 있습니다. 가령 k가 143(=11*13)이라고 해봅시다. 어떤 자연수의 자릿수를 아주 열심히 곱해서 k의 배수를 만들 수 있을까요? 11도 13도 없는데요? 그러니 k를 소인수분해할 필요는 크게 없습니다.

 

다만! 조심해야 할 점이 있는데, 많이들 실수를 하기 좋은 포인트 중 하나입니다. 문제 조건 상 "자릿수에 0이 포함되어 있으면 k가 무엇이든간에 해당이 되"기 때문에, k에 11 이상의 소인수가 있다고 해서 0을 출력해서는 안됩니다.

 

그렇다면 본격적으로 문제 풀이에 들어가보겠습니다. 우선은 1부터 n까지의 수 중에서 k-special한 숫자가 몇 개 있는지를 구하는 함수를 정의하고, 이 함수가 적당한 시간(O(logN)정도)에 돌아간다면 문제를 어렵지 않게 풀 수 있습니다. 그렇다면 우선은 0부터 n까지의 수 중 k-special한 수는 어떻게 개수를 구하는지 생각해보면 되겠습니다.(굳이 1이 아니고 0인 이유는 아래에서 설명됩니다.)

 

가장 합리적인 방법은 역시 앞자릿수를 기준으로 생각하는 것입니다. 가령 n이 54321이고 k가 12라고 해봅시다. 만의 자릿수가 0인 경우는 0부터 9999까지가 있으며, 이는 n이 9999, k가 12일 때의 k-special한 수를 구하는 것과 같습니다. 그렇다면 만의 자릿수가 1인 경우, 즉 10000부터 19999까지도 마찬가지로 하면 될까요? 2인 경우, 3인 경우도 그럴까요?

 

첫 자릿수가 1 이상인 경우에는 추가적으로 생각해줘야 할 부분이 있습니다. 단순히 맨 앞자릿수를 떼고 k를 넘겨준다고 해봅시다. 맨 앞자릿수는 1이기 때문에, 이걸로는 k에 영향을 끼치지 않습니다.(2나 3이었다면 12에서 2나 3을 나눈 만큼으로 k가 바뀝니다.)즉, 만의 자릿수가 0인 경우와 같이 9999까지의 k-special한 수를 구하면 될 것 같네요.

 

하지만 여기서 그대로 구현하면 문제가 생깁니다. 바로 1, 2, 3...과는 달리 10001, 10002, 10003...은 0이 포함되어 있는 수라는 것입니다. 그래서 10001, 10002, 10003,....은 모두 k가 무엇이든 간에 k-special한 수가 됩니다. 이런 경우를 처리하기 위해서, 저는 정의한 함수 f에 추가적인 인자로 iszero(leading zero를 생각해야 하는 경우인지, 그렇지 않은지를 구별)라는 것을 넣었습니다.

 

이런 방식으로, 만의 자릿수가 2인 경우라면 맨 앞의 자리에서 2가 곱해지니까 k를 2로 나눈 6을 넣어주면 될 것입니다. 그 뒤로도 마찬가지고요. 조금 더 엄밀하게 말하자면, 맨 앞의 자리가 i인 경우에는 k//gcd(k, i)가 다음 함수에 들어간다고 생각하면 됩니다. 메모이제이션을 잘 사용해서 재귀 함수를 사용하거나 dp를 하는 등의 방법을 잘 사용한다면 시간복잡도 문제 없이 함수를 구현할 수 있습니다.

 

다만 여기서 실수할 수 있는 부분이 아주 많아서 실제 대회에서의 난이도를 크게 올렸는데요. 우선 첫번째로는 위에서 언급한 '자릿수에 0이 포함된 경우'가 있을 겁니다. 저는 저 실수를 하지는 않았지만, 'n이 한자릿수일 때 구하는 로직'을 잘못 짜서 한번 틀리고, 'n이 101, 102...와 같이 처음부터 0이 들어가 있는 수일때' 로직을 잘못 짜서 한번 틀리고, 20분만에 풀고 퍼솔할 수 있던 문제를 3시간이나 걸려서 풀게 된 원인이 되었습니다.

 

구체적인 로직 구현은 아래 코드에서 확인해보시면 될 것 같습니다.

from math import gcd
k,l,r=map(int,input().split())
mod=10**9+7
mem=dict()
def f(n,k,zero):
	if (n,k,zero) in mem:return mem[(n,k,zero)]
	res=0
	if k==1:
		res=n+1
	elif n<10:
		for i in range(n+1):
			if i%k==0:res+=1
	else:
		ct=0
		first=n
		while first>9:
			first//=10
			ct+=1
		other=n%(10**ct)
		if zero:
			res += 10**ct
		else:
			res += f(10**ct-1, k, False)
		for i in range(1, first):
			res+=f(10**ct-1, k//gcd(k, i), True)
		if other<(10**(ct-1)):
			res+=(other+1)
		else:
			res+=f(other, k//gcd(k,first), True)
	res%=mod
	mem[(n,k,zero)]=res
	return res
print((f(r,k,False)-f(l-1,k,False))%mod)

 

저는 메모이제이션을 활용한 재귀함수로 문제를 풀었습니다. python으로도 여유롭게 시간 안에 돌아가고, 대회에서도 거의 비슷한 코드를 제출해서 AC를 받았습니다.

 

추가적인 질문, 궁금한 사항이 있으시다면 언제든 질문은 환영합니다. 감사합니다!