BOJ 2225 합분해

예전에 여러 번 풀었고, 간단한 dp문제 같아 보이지만 중요한 문제이다.
지금부터 다시 복습해 보겠다.

0부터 N까지의 정수 중 k개를 더 해서 그 합이 N이 되는 경우의 수를 구해야 한다.
그리고 덧셈의 순서가 바뀌면 다른 경우로 센다(1+2와 2+1은 다르다.) 또한 한 개의 수를 여러번 써도 된다.

d[N][k] = k개를 더해서 그 합이 N이 되는 경우의 수
로 놓으면, d[N][k] = SUM(x=0~N)d[N-x][k-1]; 로 하면 될 것 같다. N이 200, k가 200이므로 O(N세제곱)만에 될 것 같다. 구현해 봐야겠다. 구현에 좀 실수가 있어서 WA를 두 번 받고 결국 AC를 받았다. 재귀로 구현했는데, 24ms의 시간이 나온다. 이것을 for문 dp로 구현하면 조금 더 시간이 줄어들 것이다. 한 번 구현해 보겠다. WA를 한 번 받고, AC를 받았다. 시간은 16ms로 줄었다. 자 이제 이것을 0ms로 줄여볼 차례이다.

먼저 d[n][k]는 항상 d[n-x][k-1]값들의 합으로만 이루어져 있으므로 즉, k-1번째 값들만 이용하기 때문에 sliding window기법을 써서 메모리를 확 줄일 수 있다.
하지만 많은 WA를 받았는데, 여기서 주의해야 할 것은 d[n][k%2]는 d[n-x][k-1]값들의 합인데, sliding window기법을 쓸 때는 0으로 초기화가 되있지 않을 수 있기 때문에 항상
d[n][k%2]값을 0으로 초기화해줘야 한다. 그렇지 않으면 전에 있던 값에 누적해서 덧셈이 되어 엉뚱한 값이 나오게 된다. 결국 AC를 받았는데, 이 역시 16ms...메모리는 줄었지만, 시간은 줄지 않았다. 왜냐하면 여전히 O(N세제곱)이기 때문이다. 시간을 줄이기 위해서는 다른 방법이 필요하다.

for문 dp로 할 때 쓸 수 있는 방법인데, for문을 보면 3중 for문이다.
d[n][k]가 있으면, for문 2개는 n과 k를 담당하고, 가장 안쪽 for문에서 x를 담당하는데,
d[n][k]=SUM(x=0~n) d[n-x][k-1] 이므로 가장 안쪽 for문이 x=0~n까지 돌게 된다.
그런데, 잘 보면 d[n][k]에 더해지는 수들은 d[0][k-1]~d[n][k-1] 이다. 이 값들은 (제일 바깥쪽 for문이 k를 담당하는 for문 이라면) 직전에 구한 값들이다. 그렇기 때문에 d[n][k]를 구하기 직전에 d[n][k-1]값들을 구하면서 이 값들의 부분합(누적합)을 미리 저장해 놓으면 3중 for문에서 x를 담당하는 가장 안쪽 for문은 돌 필요가 없다.
이렇게 하면 결국 O(N제곱)만에 가능하다. 게다가 sliding window까지 쓰면 메모리도 줄일 수 있다. AC를 받았다.