백준 20500

[amm0124]

문제

백준 20500번을 풀었습니다.
백준 20500 : https://www.acmicpc.net/problem/20500

설명

0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 구하는 문제입니다.

접근법

15의 배수에 대해 생각해봅시다. 15의 배수는 3의 배수이자, 5의 배수여야 합니다.

• 5의 배수 : 일의 자리가 0 또는 5여야 함.
• 3의 배수 : 모든 자릿수의 합이 3의 배수여야 함.

이를 기억하고 문제를 해결합시다.

해설

n<=1515입니다. 15가 참 많이 들어간 문제입니다. 1515자리 양의 수를 직접 구하는 문제는 절대 아닐 것입니다. 그랬다간 OOM이 되어버릴 테니까요. 일단 15의 배수여야 하니 일의 자리는 5로 고정일 것입니다. 그러면 일의 자리를 제외한 나머지 자릿수의 합의 나머지가 1이 되면 (1+5)%3==0이 되므로 15의 배수가 성립하겠네요.

그렇다면, n자리 수의 일의 자리 수는 5이므로, n-1 자리의 합을 3으로 나눈 나머지를 1로 만들어야합니다. 뭔가 느낌이 중복되는 구조 -> dp 냄새가 나는데, 조금 더 말로 풀어보겠습니다. 내가 n-1자릿수의 숫자 %3의 값을 안다면, 이를 통해 n자릿수의 숫자 %3을 쉽게 알 수 있습니다. 즉, 점화식을 구할 수 있다는 것입니다.

n자리 수에서, 3으로 나눈 나머지를 i라 할 때 (i=0,1,2,가 되겠네요!), dp[n][i]를 가능한 숫자의 수라고 하면,
dp[n][0] = dp[n-1][1] + dp[n-1][2] (뒤에 5를 붙이는 경우 + 뒤에 1을 붙이는 경우)
dp[n][1] = dp[n-1][0] + dp[n-1][2] (뒤에 5를 붙이는 경우 + 뒤에 1을 붙이는 경우)
dp[n][2] = dp[n-1][0] + dp[n-1][1] (뒤에 5를 붙이는 경우 + 뒤에 1을 붙이는 경우)
로 쓸 수 있습니다.

우리는 끝자리가 5로 고정되어 있으므로, dp[n-1][1]을 구하면 정답이 되겠네요!
저는 거꾸로 배열을 선언했습니다!

소스 코드

N=(int)(input())
dp = [[0]*(N+1) for _ in range(3)]
dp[1][1]=1
dp[2][1]=1
for col in range(2,N) :
    for row in range(3) :
        for index in range(3) :
            if row!=index:
                dp[row][col]+=(dp[index][col-1])      
        dp[row][col]=dp[row][col]%1000000007        
print(dp[1][N-1])

마무리하며

이번주는 dp만 푼.. ~ 다음 주부턴 그래프도 풀어보겠습니닷.