;ㅂ; 너무 빠르게 힌트드리는거일 수 있지만,

1, 2가 더해지는 경우의 수는 2개입니다.
여기서 3이라는 수를 더한다 가정합시다.
그럼 나오는 경우는 다음 6가지입니다.

1 2  3
2 1  3

1  3  2
2  3  1

3  1 2
3  2 1

3의 위치에 따라 경우의 수가 달라지게 되므로, 다음과 같이 생각할 수 있습니다.
기존의 수가 i개일 때, i+1번째 수가 들어가게 되는 경우 경우의 수는
Case[i+1] = (i+1) * Case[i]

이걸 CC에 접목시켜봅시다.

이거보다 더 쉬운 방법이 있을것도 같은데 ?.?
당장 아이디어가 떠오르지 않네요.
제가 생각하는 아이디어는 이렇습니닷..

오우 기발하네요~ 감사합니다 조금있다가 들어가면 한번해봐야겠어요~

그런데 궁금한점이

현재 사용한 동전이 1 1 이고 지금 사용할 동전이 1 일때

(1) 1 1 / 1 (1) 1 / 1 1 (1)

이 경우는 같다고 보지 않을까요

저거 코딩해봤는데 O(N^4) 나오네요. ㅋㅋㅋㅋ

D[i][j] = j개의 숫자로 i를 만들 수 있는 경우의 수

라고 문제를 정의하면 다음과 같은 "확장 방법"으로 문제를 해결할 수 있습니다.

"0~n개의 숫자를 골라서 j+1번째 위치에 수를 결정합니다."

위의 방법을 k번 수행하면 k개의 숫자를 모두 결정할 수 있게 되며, 각 위치에 따른 숫자가 결정되기에 중복되는 경우를 모두 뺄 수 있겠네요.

이 방법의 시간복잡도는 O(N^3)이 되겠네요.

이해안되시면 댓글 달아주세요 ~_~

고맙습니다 ㅋㅋ

너무나도 많은 DP를 한번에 풀다보니;;

점화식 세우는 버릇이 꼬여버려서;;;;;;

하여튼 고맙습니다~ 도움이 많이 됬어요 ^ㅡ^