문제 개요
하나의 숫자 n이 주어졌을 때, 각 자릿수가 엄격하게 오름차순으로 배열된 n자리 양의 정수가 총 몇 개 존재하는지 구하는 프로그램을 만들어 보겠습니다.
예를 들어 입력값이 n = 3이라면 출력은 84가 됩니다. 그 이유는 123, 124, 125, ..., 678, 789처럼 각 자릿수가 뒤로 갈수록 반드시 커지는 세 자리 수가 정확히 84개이기 때문입니다.
풀이 접근 방법
이 문제의 핵심은 조합(Combination) 개념에 있습니다. 엄격하게 증가하는 숫자를 만들 때 사용할 수 있는 자릿수는 1부터 9까지 총 9개뿐입니다. 여기서 n개의 숫자를 선택하면, 선택된 숫자들을 나열하는 순서는 오름차순 단 한 가지로 고정됩니다. 따라서 가능한 경우의 수는 곧 조합 공식 9Cn과 같습니다.
- n이 9보다 작고 0이 아니라면, 조합 9Cn의 값을 반환합니다.
- 그 외의 경우(n이 0이거나 허용 범위를 벗어나면)에는 0을 반환합니다.
즉, 복잡한 탐색 없이 하나의 조합 공식만으로 답을 즉시 계산할 수 있어 매우 효율적인 풀이입니다.
구현 예제
from math import factorial as f
class Solution:
def solve(self, n):
if n < 9:
return f(9) / f(n) / f(9 - n)
else:
return 0
ob = Solution()
print(ob.solve(3))
위 코드는 math 모듈의 factorial 함수를 가져와 팩토리얼 기반으로 조합 공식 C(9, n) = 9! / (n! × (9-n)!)을 계산합니다. 조건에 맞지 않는 입력은 0을 반환하여 처리합니다.
실행 결과 확인
입력
3
출력
84
n = 3일 때 결과가 84로 출력되며, 이는 앞서 살펴본 예상 값과 일치합니다. 이 알고리즘은 단순히 팩토리얼 연산 몇 번만 수행하면 되므로 시간 복잡도 역시 사실상 상수 수준으로 매우 빠릅니다.