분할수 1 timer 1s memory 256MB

자연수 n을 순서를 고려하지 않고 1개 이상의 자연수의 합으로 나타내는 경우의 수를 분할수라고 한다.

n에 대한 분할 수는 P_N 또는 p(n)으로 표기한다.

n = 4인 경우를 예를 들어보자.

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

5가지 방법으로 분할 할 수 있다.

따라서 P₄​ = 5 이다.

1이상 1,000 이하의 n을 입력받아 p(n)을 구하는 프로그램을 작성하시오.