BOJ 2688 - 줄어들지 않아 (Python3)

쉬운 문제 설명만 하면 제법 지루한 법이다.

그래서 가능하면 적어도 다섯 문제마다 한 번씩은 Silver V 이상의 난이도를 가진 문제의 풀이를 올리려고 한다.

풀이가 부족하지 않게 나도 빨리빨리 질주해야겠다.

 

그럼 22년 11월 10일의 마지막 포스팅, 줄어들지 않아. 무려 Silver I 난이도의 문제, 본격적으로 풀이에 돌입해 보자.

---

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다.

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T(\(1\le T\le 1000\))이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (\(1\le n\le 64\))

 

예제 입력)

3
2
3
4

 

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

 

예제 출력)

55
220
715

 

---

내 코드

import math
for i in range(int(input())):
    n = int(input())
    print(math.comb(9+n, 9))

 

어려워 보이는 문제에 비해서 너무 짧고 간단한 코드가 등장했다. 하지만 다른 사람들의 코드를 보면 적으면 200B, 많으면 1KB를 넘는 코드까지 튀어나온다.

무엇이 코드의 간결함을 이토록 다르게 하였는가, 이것은 수학의 문제이기 때문이다.

 

만약 당신이 고등학생이고, 이과이며, 확률과 통계를 아예 모르지 않다면 중복조합을 모르지는 않을 것이다.

그렇다. 이 문제는 중복조합 문제이다. 중복조합에 대한 이론적 설명은 이 프로그램 설명을 넘어가니 제외하고, 조금 더 쉬운 풀이방법을 찾아 보자.

0부터 9까지의 자릿수를 가지는 n자리 숫자는, 9개의 1과 n개의 =, 다시 말하여 111111111==...==을 배열하는 방법과 같다.

맨 앞자리 숫자를 맨 처음 오는 = 왼쪽의 1 갯수로, 그 다음 숫자를 두 번째 오는 =의 왼쪽에 있는 1의 갯수로, ..., 마지막 자리 숫자를 n번째 오는 = 왼쪽의 1 갯수로 정의하면, 줄어들지 않는 수와 1...1==...==의 배열은 정확하게 일대일로 대응이 된다.

예시를 들어 보자. 0039에 대응되는 문자열은 ==111=111111=이다. 1238은? 1=1=1=11111=1이 대응된다. 

 

1...1=...=의 배열 가짓수를 어떻게 구해야 할지는 잘 알 것이다. 그렇다. \(_nC_r\)이다. (대학교에서는 \(\binom{n}{r}\)로 표기하고, 수학적 공대생인 나도 그 표기법을 애용한다. 앞으로 이 표기법을 사용하자.)

총 n+9개의 문자 중 1이 들어가야 할 9개의 자리를 선택해야만 하는 것이므로, 경우의 수는 \(\binom{n+9}{9}\)가지가 나온다.

이항계수를 많이 사용해야 하는 프로그래머들은 현명하게도 미리 이런 함수를 만들어 놓는 것을 택하였다. 그것이 바로 math.comb(n, r) 함수이다.

주의해야 할 점은, 이 math.comb는 파이썬 내장 함수가 아니라 다른 라이브러리 속에 있다는 것이다. 그렇기 때문에 사용 전, 미리 이 함수를 포함한 라이브러리를 불러 온다는 신호를 주어야 한다. 그것이 바로 첫 줄에 있는 import math이다.

그 다음은 나온 함수를 가감없이 활용하여 계산하면? 끝이다. 축하한다! 당신은 Silver I 문제를 풀었다!

 

이로서 2688번의 풀이를 마친다.

 

그럼, 오늘도 당신의 코딩 실력이 상승하기를.