🧚‍♂️알고리즘🧚‍♂️ - 조합/순열 2

골드 5

1722

1722번: 순열의 순서

자릿수에 따른 순열의 경우의 수를 미리 구하기

N자리일 때 각 자리 경우의 수는

[N!개][N-1!개][ ].....

면 

 

1. k 가 주어졌을 때 값 구하기

각 자리 순열은 높은(앞) 자릿수부터 먼저 결정. 

결정시에는 뒷 자리의 경우의 수 참고.

 

2. 값이 주어졌을 때 k값 구하기

앞자리부터 봐서 순서대로 봤을 때 미사용 수가 있으면 해당 자리의 경우의 수 카운트 

from sys import stdin
N = int(stdin.readline()) # N자리

F = [0]*21 #자리별로 만들 수 있는 경우의 수 저장
F[0] = 1
for i in range(1,N+1):
    F[i] = F[i-1] * i  #팩토리얼리스트 만들기

S = [0]*21 # 순열담는리스트
visited = [False] * 21 # 숫자 사용여부

numlist =list(map(int, stdin.readline().split()))

if numlist[0] == 1: # 순열출력하기
    k = numlist[1]
    for i in range(1,N+1):
       cnt = 1 #해당 자리에서 몇 번쨰 수를 사용해야 할지 정하는 변수
       for j in range(1,N+1):
           if visited[j] : #이미 사용한 숫자는 사용할 수 없음
               continue
           if k <= cnt * F[N-i]:
               k -= (cnt-1) * F[N-i]
               S[i] = j
               visited[j] = True
               break
           cnt += 1
    for i in range(1,N+1):
        print(S[i], end = " ")
    
else: # k값 출력하기
    k = 1
    for i in range(1,N+1):
        cnt = 0 #미사용 숫자 체크
        for j in range(1, numlist[i]): #현재 수보다 작은 수들이 사용되지 않고 남아있는가??
            if not visited[j]:
                cnt += 1
        k += cnt * F[N-i]
        visited[numlist[i]] = True
    print(k)

---

골드 3

1256

1256번: 사전

 D[a의 개수][z의 개수]

 

import sys
input = sys.stdin.readline
N, M, K = map (int, input().split())
D = [[ 0 for _ in range (202)] for _ in range (202)]

for i in range(0, 201): # 조합 테이블 만들기
    for j in range (0, i + 1):
        if j == 0 or j == i:
            D[i][j] = 1
        else:
            D[i][j] = D[i - 1][j - 1] + D[i - 1][j]
            if D[i][j] > 1000000000:
                D[i][j] = 1000000001 # K 범위가 넘어가면 범위의 최댓값 저장

if D[N + M][M] < K: # 주어진 자릿수로 만들 수 없는 K번째 수의 경우
    print(-1)
else:
    while not (N == 0 and M == 0):
        if D[N - 1+ M][M] >= K: # a를 선택해도 남은 경우의 수가 K보다 큰 경우
            print ("a", end='')
            N -= 1
        else:
            print("z", end='')
            K -= D[N - 1 + M][M]
            M -= 1

ajflrk dksehfdkrkwksgdk dlfeks dlfqhgnxhlgkrh ekdmadpektlqhsek

---

골드 2

1947

1947번: 선물 전달

완전 순열 : n개의 원소의 집합에서 원소들을 재배열 할 때 이전과 같은 위치에 배치되는 원소가 1개도 없을 때

 

D[N] : N명일 때의 정답

- 양방향 교환일 때 경우의 수는 D[N-2]

- 단방향 교환일 때 경우의 수는 D[N-1] 

 

N = int (input ())
mod = 1000000000
D = [0]*1000001
D[1] = 0
D[2] = 1
for i in range(3, N+1) :
    D[i] = (i-1) * (D[i-1] + D[i-2]) % mod # 완전 순열 점화식
                    
print(D[N])

 

akcksrkwl