꾸준하게 거북이처럼

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 풀었긴했지만 시간적 효율이 안좋아서 다시 한번 생각해 보았다. 처음에 이 문제에서 점화식을 dp[n][k] = dp[n - 1][i]( i = 1 ~ k까지) 라고 두었다. 그렇게 되면 => 3중 중첩문 + 여러번 같은 수를 반복해서 더하게됨. dp[2][1] 이나 dp[2][5] 를 더할 때도 반복해서 dp[1][1 ~ k] 까지 똑같이 같은 반복으로 더해야한다. 이는 불필요하다. 아래는 위의 점화식으로 코드를 짠것이다. dp = [[0] * 201 for _ in range(201)] n, k = map(int,input().split()) for i in range(1, 20..