Boj 1336 c++ 수열의 개수 NKD

https://www.acmicpc.net/problem/1336

 

 

문제

 

 

 

접근

 

N, K, D의 제한이 모두 10만이라고는 했지만 사실 수열의 합 값인N의 제한이 10만이기 때문에 수열의 길이 제한인 K는 매우 제한된다.

수열은 증가하는 자연수 수열이기 때문에 길이가 K인 수열의 가장 작은 N은 K * (K+1) / 2 이다.

즉, K * (K + 1) <= 100000 이여야 하기 때문에 방정식을 풀어보면 K의 최대값은 446이다.

 

그리고 수열의 초기 상태를 1, 2, 3, 4, ..... K 라고 하자.  수열의 합인 K * (K + 1) / 2 값이 N 보다 작다면 우리는 그 잔차 만큼을 수열에 더해주어야 한다. 하지만 증가수열 조건을 위반하지 않기 위해서는 특정 연속한 구간에 1씩을 더해주는 연산밖에 하지 못한다.

그리고 각 항과의 차이 제한이 D임을 고려하면 현재 1부터 K 까지의 연속한 자연수 수열에서 연속한 두 항의 차이는 1이기에 특정 구간에 1을 더해주는 연산은 최대 D-1번 밖에 할 수 없다.

 

즉, 구해야 하는 경우의 수는

S = N - K * (K+1) / 2

(S >= 0) 일 때

일정 길이의 연속한 구간에 1을 더해주는 연산(1, 2, 3, ... K) 를 각각 최대 D-1 번 사용하여 현재의 잔차인 S를 만들 수 있는 경우의 수를 구하는 것이다. 이를 통해 해당 문제는 무제한 용량 배낭문제로 변형된다.

 

 

풀이

 

1, 2, 3, 4 ..... , K-1, K 을 오름차순으로 고려한다고 가정했을 때 dp 배열의 정의는 

" dp[ i ][ j ] =  i번째 연산까지 고려하였을 때 누적합을 j 로 만들 수 있는 경우의 수 " 이다.

 

하지만 점화식이 문제이다. 정말 정말 문제이다. 처음 문제를 접했을 때 상태 전이 방식을 파악하는 난이도가 극악이다.

 

처음에 생각한 방식은 현재 j를 채울 때 i 연산을 사용할 수 있는지 여부를 확인한 후, 한번이라도 사용할 수 있다면 

채운 후, i 를 D 번 이상 사용할 수 있는 경우는 제외하는 것이였다.

   for(int i = 1; i <= K; i++) {
        for(int j = 0; j <= S; j++) { // 가치의 합
            if(j >= i && j / i < D) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % MOD;
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

 

하지만 이는 당연하게도 틀린 방법이다. 현재 연산을 D 번 이상 사용할 수 있음에도 D - 1번 이하로 사용하는 경우를 제외해버리기 때문이다.

올바른 방식은 j가 D * i 이상인 경우에 D번 이상 사용하는 경우 자체를 제외하는 것이다.

 

점화식을 자세히 보자.

 

dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % MOD

 

dp[ i ][ j - i ] 의 의미는?

우선 ' j ' 즉, 현재 목표 누적합량에서 i를 제외하는 것은 무슨 의미일까? 

j 를 완성하기 위해서 i 를 최소 한번은 사용한다는 뜻이 될 것이다. 그리고 동시에 i번째 연산까지 함께 고려하므로

해당 점화식은 i번째 연산을 전혀 사용하지 않는 경우 dp[i-1][j] 와 함께 i번째 연산을 최소 한번 사용하는 것 부터 최대로 사용하는 경우까지 모두 포괄하는 '무한 배낭'의 형태가 되는 것이다.

 

우리는 여기서 i 를 D 번 이상 사용하는 경우를 제외해야 한다.

여기서 고려해야될 점은 우리는 현재 목표 누적합 값  ' j '를 작은 값 부터 큰 값까지 오름차 순으로 계산하고 있다는 점이다.

j 가  D * i 보다 작은 경우들에 대해서는 당연하게도 적용되지 않으며, j가 정확히 D * i 값이 되는 순간에는 i 를 D만큼'만' 사용한 경우를 빼주면 된다.

 

dp[i][j] = (dp[i][j] - dp[i-1][j - D * i] + MOD) % MOD;
/*
	i를 정확히 'D'번 사용한 경우만 제외한다
*/

 

하지만 왜 D만큼 사용한 것만 빼주는 것일까? D +1 , D + 2만큼 사용한 것들 또한 고려해주어야 하지 않는가?

 

라고 생각할 수 있다. 하지만 점화식을 다시 들여다보면 의문이 해소된다.

 

dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % MOD;

 

우선 위에서 우리는 j 값이 정확히 D * i 가 되는 지점에서 D번 사용하는 경우를 제외해주었다.

이제 dp[i][D*i]에는 i를 최대 D-1번 사용하는 경우 밖에 안남아있다.

dp[i][D*i] = (dp[i][D*i] - dp[i-1][D*i - D*i] + MOD) % MOD;

 

이번에는 j값이 i * (D+1)인 경우를 생각해보자.

dp[i][i * (D+1)]       =      i를 사용하지 않는 경우 + dp[i][i * (D+1) - i] (i를 최소 1번 사용하는 경우의 수) 이다.

dp[i][i * (D+1)] 값을 분석해보면 이전에 계산했던 값이지만 용량이 늘어나며 정의가 바뀐다.

 

dp[i][i * (D + 1) - i] = dp[i-1][D * i] (i를 한개 사용하는 경우의 수) + dp[i-1][D * (i-1)] (i 를 두개 사용하는 경우의 수) ........................dp[i-1][0] (i를 D + 1개 사용하는 경우의 수)

하지만 마지막 값 dp[i-1][0] 값은 이전 식에서 이미 제거되었다.

즉, 현재 계산식에서 제외해주어야 하는 유일한 값은 이전 상태에서는 D-1개를 사용하는 경우였지만 누적합 값이 늘어나며 D개를 사용하게 된 dp[i-1][j - D * i] 값만 제외해주면 된다는 것이다.

 

 

이걸 어떻게 알아

 

 

 

정답코드

 

#include <iostream>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int dp[447][100001]; /*
 조건을 만족하는 K의 최대값은 446이다.
 정의 : i번째 까지 고려했을 때 합이 j가 될 수 있게 하는 경우의 수
 ** i번째 수는 최대 D-1번 더한다
 */

int main() {

    ll N, K, D;
    ll S;

    cin >> N >> K >> D;

    S = N - K * (K + 1) / 2;

    if(S < 0) {
        cout << "0";
        return 0;
    }

    for(int i = 0; i <= K; i++) {
        dp[i][0] = 1;
    }

    for(int i = 1; i <= K; i++) { // 고려하고 있는 숫자들
        for(int j = 0; j <= S; j++) { // 가치의 합
            int k = i, cnt = 1;
            if(j >= k) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-k]) % MOD;
                if(j >= D * i) {
                    dp[i][j] = (dp[i][j] - dp[i-1][j - D * i] + MOD) % MOD;
                }
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[K][S];
}

 

 

 

dp의 세계는 정말 끝도 없다...