41. 순서를 생각하는 수분할 알고리즘 (재귀 프로그래밍)

1. 개요

순서를 생각하는 수분할 알고리즘은 쉬움.

점화식은 P(n) = P(n-1) + P(n-2) + ... P(1) + 1

모든 경우를 다 따지는 것이기 때문에 메모이제이션을 못씀.

중복이 일어나지 않음.

그렇게 조사해보면

결국 

1 | 1 1 | 1 1 1 | 1 1 1 1 | ....

무수한 1의 나열에서 각 자리에 맞게 | 기호를 넣는 경우의 수와 같음

즉, 최종적으로 경우의 수는 2^(n-1) 이다.

2. 문제

순서를 생각하는 수분할 알고리즘을 작성하시오.

3. 코드

3-1) 코드

3-2) 출력

4. 정리

수분할 알고리즘은 재귀 프로그래밍 사고의 기초 부분 중 하나.

추가적인 생각점: 순서에 상관없이 각각의 수분할 경우에 대한 숫자 나열을 출력하시오.