백준 2225번 - 파이썬

2225번: 합분해

문제를 풀었긴했지만 시간적 효율이 안좋아서 다시 한번 생각해 보았다.

처음에 이 문제에서 점화식을 

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, 201):
    dp[1][i] = i

for i in range(2, 201):
    for j in range(1, 201):
        res = 0
        for m in range(1, j + 1):
            res += (dp[i - 1][m] % 1000000000)
            
        dp[i][j] = (res % 1000000000)
print(dp[n][k])

 

dp[n][k] = dp[n - 1][i]( i = 1 ~ k까지) 
이 말은 즉, i 가 1 ~ k -1 일 때 dp[n][k - 1]로 나타낼 수 있으며 여기서 dp[n - 1][k] 만 더해주면 dp[n][k]가 된다.

 

 

최종 점화식
dp[n][k] = dp[n][k - 1] + dp[n - 1][k]

 

코드

dp = [[0] * 201 for _ in range(201)]
n, k = map(int,input().split())

for i in range(1, 201):
    dp[1][i] = i
for i in range(1, 201):
    dp[i][1] = 1

for i in range(2, 201):
    for j in range(2, 201):
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000

print(dp[n][k] % 1000000000)

# dp[n][k] = dp[n - 1][i]( i = 1 ~ k까지) => 이를 그대로 쓰면 3중 중첩문 + 여러번 같은 수를 반복해서 더하게됨.
# 하지만, dp[n - 1][i] 에서 i = 1 ~ k - 1 일때 => dp[n][k - 1] 와 같다.
# 따라서 dp[n][k] = dp[n][k - 1] + dp[n - 1][k]로 점화식을 간단히 할 수 있다.

아래 사진을 보면, 시간적 효율성이 훨씬 더 좋아진 것을 확인할 수 있다.