BAEKJOON_2225) 합분해

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 다이나믹 프로그래밍 

2225) 합분해 (19.03.21) (19.09.30)

* 6달 전에꺼랑 비교했을때 새로 알게  된 것들이 많은 것 같다.
* StringTokenizr()를 쓸 수 있게 되었고, bw.write()에서 제대로 출력하는 법도 알았다.



* 덧셈의 순서가 바뀌어도, 한 개의 수를 여러개 써도 다 다른경우로 봐야하는 문제.
* 이 문제도 마지막에 더해지는 숫자를 기준으로 이차원 배열을 만들었다.

* 총 합이 n 일 때, k가 1일때, 2일때 ... 이렇게 자리수를 늘려가면서 배열을 채워보니
* 규칙을 찾을 수 있었고, 식으로 만들었다.
* 여기서 답을 1000000000 으로 나누어야 했고, 중간중간에 나누어 주었다.

* 마지막에 더해지는 수를 L 이라고 했을 때,
* D[K][N] = SUM(D[K-1][N-L]), (0<=L<=N).
* 채워야 하는 칸의 수는 n*k, 그리고 한 칸은 0부터 n 까지 n 이므로
* 시간복잡도는 k*(n^2) 이다.