I am developing person.

https://www.acmicpc.net/problem/13908

import sys
from math import comb
input = sys.stdin.readline

n, m = map(int, input().split())
cnt, result = 10, 0;
for i in range(m+1): result += ((-1)**i)*(cnt**n)*comb(m,i); cnt-=1
print(result)

point 1 : 시간 제한 1초

알고리즘 분류가 브루트포스이기에, 모든 경우의 수를 따져본다고 생각할 수 있으나, 시간제한이 1초이기에 최대 경우 7^10인 반복문을 다 돌리기에는 무리가 있다. 따라서, 답을 도출할 수 있는 식을 만들어야한다는 생각을 해볼 수 있다.

soltion

n의 길이를 가지는 비밀번호가 m개의 수를 포함함을 미리 알 수 있다. 이때, m개의 수가 무엇인 지는 중요 요인이 아니다. 몇 개의 서로 다른 숫자를 포함하는 n 길이 숫자이냐만 논의해야할 부분이기에, n과 m값만을 가지고 연산을 진행한다. 이때 수학적 개념인 포함 배제의 원리를 사용하게 되는데, 이는 가능한 모든 경우의 수에서 해당하지 않는 경우의 수를 제해주는 원리이다. 원리에 대한 자세한 설명보다는, 주어진 입력에서 어떻게 동작하는 지를 우선시하여 설명해보자면,

case 1: n = 2, m = 1
# i = 0
1*(10**2)*comb(1,0) # 100 = 가능한 모든 경우의 수
# i = 1
(-1)*(9**2)*comb(1,1) # -81 = m이 들어가지 않은 수
case 2: n = 2, m = 2
# i = 0
1*(10**2)*comb(2,0) # 100 = 가능한 모든 경우의 수
# i = 1
(-1)*(9**2)*comb(2,1) # -162 = m0이 들어가지 않은 경우 +  m1이 들어가지 않은 경우
# i = 2
1*(8**2)*comb(2,2) # 64 = m0과 m1이 모두 들어가지 않은 경우 (i=1의 연산에서 겹쳐서 빼지므로 다시 더해줌)

이와 같이 반복문을 돌며, 전체 경우의 수에서 필요한 부분을 제해주는 것을 볼 수 있다.

참고