Python 백준 2225-합분해

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

문제 해결

• 이 문제의 접근도 2차원리스트로 dp 리스트를 만들어 접근해야된다
• 숫자 n을 k개의 숫자로 나타내는 갯수를 어떻게 알아낼것인가?
  • 이 생각을 30분정도 해도 떠오르지 않아, 무작정 귀납법 방법을 사용하여 규칙을 찾아냈다

그림을 통해 귀납적 방법 추론

이해를 돕기위해 그림을 그려봤습니다(악필이여도 이해부탁드립니다😂)

이 그림을 통해 점화식을 구할수있게 됐습니다.

dp[k][n]= dp[k-1][n] + dp[k][n-1]

전체코드

import sys
input=sys.stdin.readline
n, k=map(int, input().split())
dp=[[0]*(201) for _ in range(201)]
for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1
for i in range(2, 201):
    dp[i][1]=i
    for j in range(2,201):
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])% 1000000000
print(dp[k][n])

정리

머릿속으로 점화식을 구하기 어렵다면, 무작정 표를 그려 규칙을 찾아 보자!