문제 해결 전략

• 지금까지 점화식 작성한 대로 특정 값 X를 기준으로 해서 작성하는 문제가 아니다.

기준을 다르게 봐야 한다.

• 1의 합으로 만드는 방법인데 1부터 n번 까지 숫자를 만들 수 있나?

• 2의 합으로 만드는 방법인데 1부터 n번 까지 숫자를 만들 수 있나?

• 3의 합으로 만드는 방법인데 1부터 n번 까지 숫자를 만들 수 있나?

• 어떤 number 를 가지고 혼자만 가지고 진행하지 말고, 전체를 가지고 봐야 한다.
  -> 이렇게 보면, dp[4] 에 대한 식을 작성하기 어렵다.
  

이런식으로 해야 한다.

---

기준을 X가 아닌 1,2,3을 가지고 숫자를 만들 수 있는지 봐야 한다.

문제에서 1,2,3 의 합으로 만드는 방법이고, 나열 한 후 생각해보자.

• 1) 1을 가지고 1부터 4까지 만드는 방법

  1 : 1
  2 : 1 + 1
  3 : 1 + 1 + 1
  4 : 1 + 1 + 1 + 1
  -> 점화식 dp[x] += dp[x - 1]
  // 모든 경우의 수 이므로 더하자.

• 2) 2를 가지고 1부터 4까지 만드는 방법

  1 : x
  2 : 2
  3 : 2 + 1
  4 : 2 + 1 ([3] 그대로 가지고 옴. ), 2 + 2 ([2] 경우의 수에서 + 2를 함.)
  dp[3] = dp[2]
  dp[4] = dp[2] + dp[4]

-> 좀 다르다. 조건이 필요 할 듯 하다.

• 3) 3을 가지고 1부터 4까지 만드는 방법.

1 : x
2 : x
3 : 3
4 : 1 + 3
dp[3] = dp[0]
dp[4] = dp[3]