흙금이네 블로그

아이디어 DP로 완전순열을 구한다. 풀이 #1 (Python) 점화식을 구하기 위해 임의로 학생과 기숙사에 번호를 매기고, 1번 학생이 K번 기숙사에 배정되는 경우를 고려한다. K번 학생이 1번 기숙사에 배정되는 경우의 수는 1번 학생과 K번 학생을 제외하고 학생 수가 N-2인 경우의 수와 같다. K번 학생이 1번 기숙사에 배정되지 않는 경우의 수는 1번 학생을 제외하고 학생 수가 N-1인 경우의 수와 같다. K는 1을 제외한 N-1개의 수가 가능하므로 두 경우의 수를 더하여 N-1만큼 곱하면 학생 수가 N인 경우의 수를 구할 수 있다. import sys input = sys.stdin.readline def solution(): T = int(input()) dp = [0]*21 dp[2] = 1 f..