[백준] 2225번(합분해)

백준 2225번

처음 제출한 코드

number, part = map(int, input().split())

dp = [0]*number + [1]

for i in range(part-1):
  for j in range(len(dp)):
    ele = 0
    for k in range(j, len(dp)):
      ele += dp[k]
    dp[j] = ele%1000000000

print(sum(dp)%1000000000)

.
◼ 동적 프로그래밍

• 마지막 숫자만을 2개로 분할해가며 1개로 분해했을 때, 2개로 분해했을 때 이런 식으로 늘려가면서 케이스를 세어주면 됨
  ex) 6을 1개로 나누면 6, 2개로 나누면 (0,6), (1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 0), 마지막 숫자를 또 2개로 분할 (0, 0, 6), ... (0, 6, 0)

.
◼ 케이스 세기

• 6으로 끝나는 조합은 이전 단계에서 6으로 끝났던 조합의 개수 합
• 5으로 끝나는 조합은 이전 단계에서 6과 5로 끝났던 조합의 개수 합
• ...
• 0으로 끝나는 조합은 이전 단계에서 6, ..., 0으로 끝났던 조합의 개수 합
  
• 그러나 생각해보니 배열의 값을 업데이트 하는 부분을 저렇게 작성할 필요가 없음
  
• 위의 내용을 반영하여 코드를 수정
  .

최종 제출 코드

number, part = map(int, input().split())

dp = [0, 1] + [0]*number

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

print(sum(dp)%1000000000)

.

◼ 실행 속도 향상