어떠한 정수 n 이 주어지면, n을 만들수 있는 합의 경우의수를 출력한다. ( 자기 자신 하나의 합은 제외 한다.)
입력 : 정수 n을 입력받는다. (2 <= n <= 60)
출력 : 경우의 수를 첫줄에 출력한다. 수는 같은데 더하는 순서가 다르면 다른 경우로 판단한다. 즉 7은 (2+2+3) ,( 1+2+3+1) 등 많은 방법으로 나타낼 수 있다. 그러나 (2+2+3), (3+2+2), (2+3+2) 등은 다른 경우의 수로 계산한다.
입력예시 : 7
출력예시 63
다이나믹 프로그래밍으로 접근해서 설명좀 해주세요 ㅠㅠ
차근차근 설명좀 부탁 부탁드립니다~~
제발 부탁드리빈디다 1주일째 이 한문제에 매달려있습니다
모든 다이나믹 프로그래밍 문제는 문제를 recurrence equation으로 나타낼 수 있어야한다
상위문제와 하위문제간의 관계를 찾을려고 나열도 해보고 직접 그려서 해보기도 했는데... 도저히 접근 방법을 모르겠네요... 얼핏보면 계단오르기와 비슷한 문제같기도 하고 ㅠㅠㅠ 너무 오랫동안 헤메다보니... 좀 도와주세요.. 리커시브로도 접근할 방법을 못찾겠습니다 ㅠㅠ
규칙을 찾아서 식을 짜내라
ㅠㅠㅠㅠㅠㅠ DP 푸는 개념은 알겠는데 이 문제에 적용이 안되서... 식좀 부탁드려요 ㅠㅠ
nc(N) = { [1,nc(N-1)], [2,(nc(N-2)], .... [N-1, nc(1)] }