숙소 배정
면접 대비시간 제한2초메모리 제한512 MB
5 이상 100 이하의 정수 n을 5 이상인 수들의 순서 없는 합으로 나타내는 방법 수를 구합니다.
문제
싱가포르에서 열리는 유스 올림픽에서 조직위원회는 각 팀을 여러 숙소에 나누어 배정하려고 한다. 숙소 하나에는 5명 이상이 들어가야 한다. 팀 인원은 종목에 따라 5명에서 100명까지다.
예를 들어 팀이 16명이면 배정 방법은 6가지다. 16명을 한 숙소에 모두 넣거나, 5명과 11명으로 나누거나, 6명과 10명으로 나누거나, 7명과 9명으로 나누거나, 8명씩 두 숙소로 나누거나, 5명과 5명과 6명으로 세 숙소에 나누면 된다. 팀이 커지면 이 목록은 꽤 길어진다.
조직위원회는 인원 을 읽어 숙소마다 5명 이상이 되도록 나누는 방법의 수 을 계산하는 프로그램을 원한다. , , 처럼 순서만 다른 배정은 한 가지로 센다. 그래서 이고, 이며 (, , , , , , ), 이다.
입력
정수 하나가 주어진다. ()
출력
을 정수 하나로 출력한다. 이 100 이하이므로 은 십진수로 최대 일곱 자리다.