(문제링크)

$O$부터 $n$까지 정수 $k$를 더해 그 합이 $n$이 되는 경우의 수를 구하는 문제이다.

이 문제는 어떻게 풀었나

쉽게 점화식을 만들 수 있었지만, 점화식을 어떻게 활용해야할지 막막했다.

• $n$은 $k$개의 정수의 합이다. d[k][n]에 만들 수 있는 경우의 수를 저장할 것이다.
• ($x$가 $n$보다 작거나 같은 정수 일때) 위를 기준으로 $n - x$를 만드는 경우의 수는 d[k-1][n-x]에 저장된다.($k-1$개 인 이유는 $x$라는 정수가 빠졌기 때문)

• $n$이 $3$이고 $k$가 $1$일때, d[2][3]은 d[1][3-0]부터 d[1][3-3]의 경우의 수의 합이 된다. (이 문제에서는 정수의 범위는 0에서 n까지 이다)

  <정수 두 개로 3을 만드는 경우의 수>
  3 + 0
  2 + 1
  1 + 2
  0 + 3

• $1$개의 정수의 합으로 어떠한 정수를 만들 수 있는 경우는 오직 한 가지 이기 때문에 d[1][3]은 반드시 $1$이 나와야만 한다.

  long long d[201][201];
  
  for(int i = 0; i <= n; i++){
      d[1][i] = 1;
  }

• 이제 $2$개의 정수를 더해 $3$을 만드는 코드를 만들 수 있다.

  for(int i = 1; i <= k; i++){ // k의 범위는 1부터다.
      for(int j = 0; j <= n; j++){ // 0부터 n까지 정수를 더해야한다.
          for(int x = 0; x <= j; x++){
              // k개의 정수를 더해 j를 만들 수 있는 경우의수
              d[i][j] += d[i-1][j-x];
          }
      }
  }