[BOJ_Python] 20500.Ezreal 여눈부터 가네 ㅈㅈ

문제

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

 

사용 알고리즘

DP

 

풀이

고려사항

1. 1과 5로만 구성된 수인지

2. 15의 배수인지

 

후기

1. 이 문제의 경우 가능한 수의 범위가 크기 때문에 DP로 진행하였다.

2. 우선, dp배열에는 digit 자리 숫자 중에서 각 자리 수가 1 또는 5로만 구성되며,

    15로 나눈 나머지가 mod15인 경우의 수를 저장한다.

    dp[0][0]을 1로 초기 세팅을 진행한다.

3. 이후 자리수를 늘리며 이전 자리 수까지의 숫자들에서

    15로 나눈 나머지 값을 기반으로 새로운 자리 수를 추가했을 때 나머지를 계산한다.

    - 현재 나머지 mod15에 1 또는 5의 숫자를 추가하여 새로운 나머지를 계산한다.

    - 이전 자리 수까지 mod15였던 모든 경우에 대해, 1 또는 5를 추가한 숫자에서의 경우의 수를 누적한다.

 

4. DP로 풀어야겠다는 생각은 들었지만, 규칙을 찾기 어려웠다.

DP의 경우 단계 별 누적을 포인트로 두고 아이디어를 찾아나가야겠다.

 

코드

def solve(N):
    dp = [[0] * 15 for _ in range(N+1)]
    dp[0][0] = 1
    
    for digit in range(1, N+1):
        for mod15 in range(15):
            # 1을 추가하는 경우
            new_mod15 = (mod15 * 10 + 1) % 15
            dp[digit][new_mod15] = (dp[digit][new_mod15] + dp[digit-1][mod15]) % 1000000007
                
            # 5를 추가하는 경우
            new_mod15 = (mod15 * 10 + 5) % 15
            dp[digit][new_mod15] = (dp[digit][new_mod15] + dp[digit-1][mod15]) % 1000000007
    
    return dp[N][0]

N = int(input())
print(solve(N))

 

결과