순서를 고려한 분할
실버 IV의견: 0
자연수 \(N\) 을 입력받아, \(N\) 을 \(1\) 이상의 자연수들의 합으로 나타내는 방법의 수를 구하여라. 단, 이번에는 순서가 다르면 서로 다른 분할로 센다. 즉 \(3 = 2 + 1\) 과 \(3 = 1 + 2\) 는 서로 다른 방법이다.
예를 들어 \(N = 4\) 인 경우 다음 \(8\) 가지가 존재한다.
$$ 4,\quad 3+1,\quad 1+3,\quad 2+2,\quad 2+1+1,\quad 1+2+1,\quad 1+1+2,\quad 1+1+1+1 $$
\(1 \le N \le 10^6\)
첫째 줄에 자연수 \(N\) 이 주어진다.
\(N\) 을 순서를 구별하여 분할하는 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 첫째 줄에 출력한다.
4
8
\(4\) 를 순서를 구별하여 분할하는 방법은 \(4\); \(3+1\); \(1+3\); \(2+2\); \(2+1+1\); \(1+2+1\); \(1+1+2\); \(1+1+1+1\) 의 \(8 = 2^{3}\) 가지다.
1
1
\(1\) 은 자기 자신뿐이므로 \(1\) 가지.
2
2
\(2\) 와 \(1+1\) 의 \(2\) 가지.
골드 IVriseoj 작성
출처 Original
평가 및 의견
순서를 고려한 분할
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
순서를 고려한 분할