[python] 백준 - 2225 (합분해)
골드5 문제이며, 제한 시간은 2초이다.
문제
해결 과정
우선 경우의 수를 쫙 써봤다. 그랬더니 패턴이 보인다. 0으로 시작하는 수는 i - 1번째 경우의 수의 총 합 1로 시작하는 수는 i - 1번째 경우의 수에서 0으로 시작하는 경우의 수를 뺀 값
따라서 DP 배열에 i 번째에서 0으로 시작하는 경우가 몇 개인지, 1로 시작하는 수가 몇 개인지 저장해놓는다.
점화식 -> dp[i][j] = dp[i - 1][j:]
풀이
n, k = map(int, input().split())
dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
for i in range(1, k + 1):
for j in range(n + 1):
if i == 1:
dp[1][n] = 1
else:
dp[i][j] = sum(dp[i - 1][j:]) % 1000000000
print(sum(dp[k]) % 1000000000)
댓글
0아직 댓글이 없습니다.