수다닷컴

한 개 이상의 숫자들을 골라 이의 합이 N이 되는 모든 경우 수를 찾는 프로그램을 작성하고자 한다. 하지만 문제를 조금 더 재미있게 하기 위해서 다음과 같은 조건을 걸고자 한다. 합을 이루는 각 숫자들에 대해서 동일한 자릿수에 등장하는 숫자가 모두 달라야 한다.

예를 들어 3개의 숫자를 더해서 180을 만드는 경우를 생각해보자.
124
31
+ 25
----
180
이 경우 오른쪽에서 첫째 자리의 경우 4, 1, 5가 각 한번만 쓰였기 때문에 위의 조건을 만족한다. 맨 왼쪽의 경우 1만이 사용되었기 때문에 위의 조건을 만족한다. 하지만 오른쪽에서 두 번째 자리의 경우 2, 3, 2 로 2가 두 번 쓰였기 때문에 위의 조건을 만족하지 않고, 이러한 경우는 세지 않는다.

아래는 3개의 숫자를 더해서 170을 만드는 경우 중 올바른 경우의 예이다.
124
31
+ 15
----
170

제출파일의 이름은 2282.cpp로하고 실행시간은 5초를 넘을 수 없다.
입력파일은 INPUT.TXT로 한다. 입력은 한 줄로 이뤄지며 정수 N가 입력된다. N은 1이상 100 이하의 정수이다.
출력파일은 OUTPUT.TXT로 한다. 입력에 대해 가능한 경우의 가지 수를 출력한다.
6
4
다음의 경우가 문제에 주어진 조건을 만족한다.
1. 6 = 6
2. 1+5=6
3. 2+4=6
4. 1+2+3=6
20
56

신청하기