CodeDrive

문제:

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다.

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단, 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3+6+3과 12=3+3+6은 다른 방법이다.

입력:

임의의 3의 배수 자연수 n이 주어진다. (3<=n<=3000)

출력:

자연수 n을 분해하는 방법의 개수를 출력하라.

풀이방법:

고등학교 수학이 생각나는 문제다. 이 문제를 변수로 나타내면 x+y+z = n (x,y,z,n은 3의 배수) 와 같고, 이는 조합 문제와 동일하다.

1. 간결하게 표현하기 위해 모든 수가 3의 배수이므로 3으로 나눠준다. (x'+y'+z' = n//3, x',y',z'>=0)

2. 3의 배수의 자연수로 분해를 해야 하기 때문에 좌변에 3을 빼줌으로써 해결한다. (x''+y''+z'' = n//3-3, x''+y''+z''>=1), 이는 nHr을 계산하는 문제와 같아진다.(3Hn//3-3)

따라서 이를 계산하면 답을 구할 수 있다.

문제링크:

www.acmicpc.net/problem/16561