[백준][Python3] 20500 - Ezreal 여눈부터 가네 ㅈㅈ

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

20500번: Ezreal 여눈부터 가네 ㅈㅈ

초급 알고리즘 DP 강의를 수강 후 연습문제로 풀게된 문제이다.

 

문제는 간단하다

1과 5로 이루어진 N자리 수 중 15의 배수를 구하는 문제이다.

어떻게하면 이 문제를 DP를 활용하여 구할 수 있을까?

 

아무런 아이디어가 떠오르지 않았다.

그래서 그냥 무작정 써봤다.

 

1자리수

1, 5

0개

 

2자리수

11, 15, 51, 55

1개

 

3자리수

111, 115, 151, 155, 511, 515, 551, 555

 

근데 3자리수를 쓰고보니 15의 배수가 한눈에 안보인다.

일일히 나눠보는 생각을 했지만 귀찮았다.

 

그러던 중 한가지 아이디어가 떠올랐다.

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

2248번: 이진수 찾기

2248번 이진수 찾기 문제를 푸는 과정을 떠올려보았다.

N자리 이진수 중 1을 M개 이하로 사용하여 크기순으로 나열한 이진수 중

K번째 수를 구하는 문제이다.

이 문제를 풀 때, 각각의 자리수에서 얻은 값을 활용하여 다음 자리수의 값을 구하였다.

 

이 문제도 혹시 그렇게 풀 수 있지 않을까?

앞 자리수로 1 또는 5가 추가될 수 있다.

1 또는 5가 추가된다는 것은 다음과 같은 의미를 지닌다.

 

1자리수에서 2자리수로 갈 때

앞자리수로 1이 추가된다 = 10을 더한다

앞자리수로 5가 추가된다 = 50을 더한다

 

그런데 어떤 두 수를 더한 값의 나머지는

그 두 수 각각의 나머지의 합의 나머지와 같다.

10 + 16 을 3으로 나눈 나머지는 얼마일까?

3 * 8 = 24 이므로

26의 나머지는 2이다.

 

하지만 다음과 같이 구할 수도 있다.

10 = 3*3 + 1 이므로 나머지가 1이다.

16 = 3*5 + 1 이므로 나머지가 1이다.

따라서 두 수를 더한 값의 나머지는 1+1 = 2 이다.

 

이것을 이 문제에 적용해보자.

어떤 수에 10을 더했을 때 그 결과가 15의 배수

즉, 15로 나눈 나머지가 0 이려면

그 어떤 수의 나머지는 얼마여야할까?

그렇다 바로 나머지가 5이면 된다.

 

어떤 수에 50을 더했을 때 그 결과가 15의 배수

즉, 15로 나눈 나머지가 0이려면

그 어떤 수의 나머지는 얼마여야할까?

50을 15로 나눈 나머지는 15*3 + 5 에서 5이다.

따라서 어떤 수의 나머지는 10이면 된다.

 

다음과 같이

1_  /  5_ 인 수가 있다고 한다면

저 1의자리의 나머지가 왼쪽의 경우 5

오른쪽의 경우 10이면 된다.

 

따라서 2자리수 일 때 15의 배수는 15 하나이다.

 

한번 다음자리수로 확장해서 생각해보자.

1 _ _ / 5 _ _ 인 수에 대해서 생각할 때

1 _ _  = 100 + _ _ 

5 _ _ = 500 + _ _

여기에서 우리는 놀라운 점을 알 수 있다.

100을 15로 나누어보면 15*6 + 10 이므로 나머지가 10이다!

500을 15로 나누어보면 15*33 + 5 이므로 나머지가 5이다!

 

즉 10, 100, 1000, 10000, .... 의 15로 나눈 나머지는 모두 10이고

50, 500, 5000, 50000, ... 의 15로 나눈 나머지는 모두 5이다.

 

따라서 위의 경우 1 _ _ 일 때는 _ _ 의 나머지가 5인 수를 더해주고

5 _ _ 일 때는 _ _ 의 나머지가 10인 수를 더해주면 된다.

 

여기까지 생각을 했다면 이를 어떻게 dp로 바꿔줄 수 있을까?

한가지만 더 생각하면 된다.

기존 15의 배수 앞자리 수에 1과 5를 채우면 나머지가 어떻게 될까?

1을 채울 땐 나머지가 0에서 10이되고

5를 채울 땐 나머지가 0에서 5가 된다.

 

여기에서 나머지가 0, 5, 10 으로만 구성된다는 것을 알 수 있다.

(마지막자리가 1로 끝나는 경우는 나머지는 1, 6, 11 중 하나가 될 것이지만,

그 경우에는 절대로 15의 배수를 만들 수 없으므로 생각하지 않는다.)

 

그렇다면 이걸 서로 돌려가며 활용하면 된다.

 

현재 자리수에서 나머지가 0인 수의 개수는

이전 자리수에서 나머지가 5인 수의 개수 + 나머지가 10인 수의 개수 이다.

나머지가 5인수 앞에 1을 붙이면 되고

나머지가 10인수 앞에 5를 붙이면 되기 떄문이다.

 

현재 자리수에서 나머지가 5인 수의 개수는

이전 자리수에서 나머지가 0인 수의 개수 + 나머지가 10인 수의 개수 이다.

 

현재 자리수에서 나머지가 10인 수의 개수는

이전 자리수에서 나머지가 0인 수의 개수 + 나머지가 5인 수의 개수이다.

이 두가지 경우의 이유 역시 위의 이유와 비슷하다.

자리수	나머지가 0인 수의 개수	나머지가 5인 수의 개수	나머지가 10인 수의 개수
1	0	1	0
2	1	0	1
3	1	2	1
4	3	2	3

점화식이 매우 간단하다!

이제 매번 나머지의 개수를 구할 때 문제에서 말한대로 1000000007로 나눠주는 과정을 섞어주고

마지막엔 구하는 자리수의 나머지가 0인 수의 개수를 출력하면 된다.

 

구현한 코드는 다음과 같다.

# 20500 Ezreal 여눈부터 가네 ㅈㅈ
dp = [[0 for _ in range(3)] for _ in range(1516)]
dp[1][1] = 1
for i in range(2, 1516):
    dp[i][0] = dp[i-1][1] + dp[i-1][2]
    dp[i][1] = dp[i-1][0] + dp[i-1][2]
    dp[i][2] = dp[i-1][0] + dp[i-1][1]
    for j in range(3):
        dp[i][j] %= 1000000007
print(dp[int(input())][0])