[DP] 백준 20500번 - Ezreal 여눈부터 가네 - Python 파이썬

 

 

생각하기

처음에는 일차원 배열의 DP로 접근을 했었다.

N=1,2,3일떄를 써놓고 규칙을 찾아보려해도 아무런 답이 나오지 않았다...

 

결국 검색을 통해 아이디어를 얻어낼 수 있었다... (아이디어만 봤다.. 아직 실력이 많이 부족.. ㅠ)

 

1과 5만 사용하기 때문에 기존 숫자에 맨 앞에 1혹은 5를 조합하는 방식이다

예를 들어 1의 자리라면 1, 5가 있을 텐데 앞에 11, 15, 51, 55가 되는 방식!

 

그렇게 되면 10과 50을 더해주는 것인데 

15의 나머지는 10의 나머지 더하기 5의 나머지를 더한 15가 된다 -> 그래서 15는 15의 배수인것이다 (당연한 얘기지만 나머지 관점에서 봤을 떄 15잖아)

 

두수를 더할 때 두수의 나머지를 더한값과 더한 값의 나머지는 같다 -> 나머지 더한값이 15를 만들면 15의 배수네?

 

여기서 10을 15로 나눈 나머지는 10

50을 15로 나눈 나머지는 5임을 확인할 수 있는데

100을 15로 나눈 나머지도 10

500을 15로 나눈 나머지도 5임을 확인할 수 있다

 

따라서 10, 100, 1000 을 더해가는 구조에서 0이 있는 자리에 들어가는 수를 15로 나눈 나머지는 5이면 되는 것

50, 500, 5000을 더해가는 구조에서 0이 있는 자리에 들어가는 수를 15로 나눈 나머지는 10이면 되는 것

 

 

우리한테 필요한 것은 무엇? 15로 나눈 나머지가 5인 개수 / 15로 나눈 나머지가 10인 것의 개수

나머지수는 신경쓸 필요가 없다!

애초에 더하는 수들 10, 100, 100.... 와 50, 500, 5000... 의 나머지가 10과 5이기 때문에 나머지를 15로 만드려면 결국 5, 10이 필요하다

 

구현하기

다차원 배열 DP를 통해 구현할 수 있다.

dp[i][j] 

i : 자리수 -1

j : 0 - 15로 나눈 나머지가 5인 개수 / 1 - 15로 나눈 나머지가 10인 개수 / 2 - 15의 배수의 개수

 

점화식은 아래와 같이 세워질 수 있다

• 15의 배수를 의미하는 dp[i][2]
  • 10, 100, 1000.. 등 나머지가 10인 수들이 더해지므로 dp[i-1][0] -> 이전 단계에서 15로 나눈 나머지가 5인 아이들
  • 50, 500, 5000.. 등 나머지가 5인 수들이 더해지므로 dp[i-1][1] -> 이전 단계에서 15로 나눈 나머지가 10인 아이들
  • dp[i][2] = dp[i-1][0] + dp[i-1][1]
• 15로 나눈 나머지가 5인 개수를 의미하는 dp[i][0]
  • 10, 100, 1000.. 등 나머지가 10인 수들이 더해지므로 기존에 나머지가 10인 아이들에게 10을 더하면 20 -> 15로 나누면 5이기 때문에 -> 이전 단계에서 15로 나눈 나머지가 10인 아이들
  • 50, 500, 5000.. 등 나머지가 5인 수들이 더해지므로 이전 단계에서 깔끔하게 나머지가 0이었던 아이들
  • dp[i][0] = dp[i-1][1] + dp[i-1][2]
• 15로 나눈 나머지가 10인 개수를 의미하는 dp[i][1]
  • 10, 100, 1000 등 나머지가 10인 수들이 더해지므로 이전 단계에서 깔끔하게 나머지가 0이었던 아이들
  • 50, 500, 5000 등 나머지가 5이니 수들이 더해지므로 이전 단계에서 나머지가 5인 아이들에게 5를 더하면 -> 10 -> 이전 단계에서 15로 나눈 나머지가 5인 아이들
  • dp[i][1] = dp[i-1][0] + dp[i-1][2]

아래 사진은 악필이지만 끄적끄적 거려본 메모이다

 

늘 어렵고 새롭다 .. 이게 맞나? ㅎㅎ

 

import sys
input = sys.stdin.readline

N = int(input())

dp = [[0 for _ in range(3)] for _ in range(1515)]

# 초기값
# N==1일떄 
dp[0][0] = 1 # 나머지가 5인 수의 개수
dp[0][1] = 0 # 나머지가 10인 수의 개수
dp[0][2] = 0 # 1자리 수일 때 15의 배수인 수의 개수


for i in range(1, N):
    # 나머지가 5인 수의 개수 = 이전 자리수에서 15의배수인 수 개수 + 이전 자리수에서 나머지가 10인 수의 개수
    dp[i][0] = dp[i-1][2] + dp[i-1][1]
    # 나머지가 10인 수의 개수 = 이전 자리수에서 15의배수인 수 개수 + 이전 자리수에서 나머지가 5인 수의 개수
    dp[i][1] = dp[i-1][2] + dp[i-1][0]
    # 15의 배수인 수의 개수 = 이전 자리수에서 나머지가 5인 수의 개수 + 이전 자리수에서 나머지가 10인 수의 개수
    dp[i][2] = dp[i-1][0] + dp[i-1][1]

print(dp[N-1][2]%1000000007)