[BOJ, 백준] 30025 K의 배수 Python

 

DP를 적극적으로 활용하면 좋은 문제가 되겠습니다.

 

정수들의 조건이 생각보다 널널하게 주어져있었던지라, 전부 곱해줘도 10 * 100 * 1000 = 10 ** 6입니다.

계산에 있어서는 크게 문제가 없을 것 같네요.

 

해답 코드는 다음과 같습니다.

N,M,K = map(int,input().split())
p = 10 ** 9 + 7
card = list(map(int,input().split()))
card.sort()
#K로 나눈 나머지의 갯수를 카운팅 하면 되겠다, 양의 정수이므로 0이 들어가 있는 경우는 카운팅하지 않는 것으로 한다
cnt = [0 for _ in range (0,K)] #이전 단계 저장하기 위함
for i in range (0,N):
    if card[i] != 0:
        cnt[card[i] % K] += 1
#위 작업으로 한자리수인것들을 생각해보면?

for _ in range (1, M):
    new_cnt = [0 for _ in range (0,K)]
    for i in range (0,K):
        for j in range (0,N):
            t = (10 * i + card[j]) % K
            #t는 K로 나눈 나머지를 indicate
            new_cnt[t] += cnt[i]
    cnt = new_cnt

print(cnt[0] % p)

 

첫번째 반복문을 통해서 1자리의 K의 배수를 저장해줍니다.

두번째 반복문에서는 2자리 이후의 K의 배수를 카운팅해주겠습니다.

new_cnt라는 리스트를 새롭게 설정해주면서 다음과 같이 진행하면 되겠습니다.