문제 https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 설명 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N × (N-1) × … × 2 ×1 가지가 있다. 둘째 줄의 첫 번째 수가 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 구해야 한다. 먼저 순열을 ..
문제 https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 설명 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있고 알파벳 순서대로 수록되어 있다. 사전에서 K번째 문자열이 무엇인지 구해야 한다. 사전에 수록되어 있는 문자열의 갯수는 \({}_{N + M}\mathrm{C}_{M}\) 이다. 그 값이 K보다 작다면 -1을 출력하고 그렇지 않다면 query를 진행해 K번째 문자열을 찾는다. if (combination(N + M, ..
문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 설명 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. 한 사이트에는 최대 한 개의 다리만 연결될 수 있고 다리끼리는 서로 겹쳐질 수 없다. 실행결과는 M개의 사이트 중 N개를 순서 구분 없이 고르는 경우의 수를 의미한다. 따라서, 조합을 사용해야 하는데 파스칼의 삼각형을 이용하면 쉽게 구할 수 있다. 파스칼의 삼각형은 \({}_{n}\mathrm{C}_{r} = {}_{n ..
순열 n가지의 물건 중 r개의 물건을 순서 구분하여 고르는 경우의 수 \({}_{n}\mathrm{P}_{r} = \underbrace{n \times (n - 1) \times \cdots \times (n - (r - 1))}_{r\text{ numbers}} = \frac{n!}{(n - r)!} \quad(0 \le r \le n)\) \({}_{n}\mathrm{P}_{n} = n!\) \({}_{n}\mathrm{P}_{0} = 1\) 중복순열 n가지의 물건 중 중복을 허용하여 r개의 물건을 순서 구분하여 고르는 경우의 수 \({}_{n}\mathrm{\Pi}_{r} = \underbrace{n \times n \times \cdots \times n}_{r\text{ numbers}} = n..
