문제 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 이항 계수를 구하는 공식은 $_{n}\mathrm{C}_{r}=\binom{n}{r}=\frac{n!}{r!(n-r)!}$이고 이를 재귀 팩토리얼 함수를 활용해 풀이하면 된다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.bufferedWriter() val st = StringTokenizer(br.readLine()) val num = st.nextToken().toInt() val k = st.nextT..

문제 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 이항 계수를 구하는 공식은 $_{n}\mathrm{C}_{r}=\binom{n}{r}=\frac{n!}{r!(n-r)!}$ 이다. 문제는 여기서 1,000,000,007로 나눈 나머지 값을 출력해야 한다. 주어진 범위가 크기 때문에 재귀 팩토리얼만 활용하면 스택 오버플로우 에러가 발생하고 파스칼 삼각형 dp를 활용하면 시간 초과가 발생한다. 이를 해결하기 위해서 모듈러 연산, 페르마 소정리, 분할 정복을 활용해야 한다. - 모듈러 연산의 분배법칙 (A + B) % p = ((..

문제 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 파스칼 삼각형을 이용해 점화식을 만들고 이항 계수를 계산해주면 된다. 아래의 이미지는 파스칼 삼각형을 쉽게 이해할 수 있도록 설명해 준다. 파스칼 삼각형은 각 단계의 처음과 끝은 1로 채워주고 그 사이의 항들은 윗 단계에서 더해주는 것으로 계산한다. 이에 대한 수학적 증명은 아래와 같다. $$\displaystyle \binom{n-1}{r-1}+\binom{n-1}{r}=\frac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}+\frac{\left(n-1\right)!}..

문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 조합 공식을 이용하면 된다. 동쪽이 서쪽에 비해 더 많거나 같은 사이트를 가지고 있기 때문에 동쪽 M개에서 서쪽 N개 중 하나를 고르는 조합인 $_{M}C_{N}$을 구하면 된다. $_{M}C_{N}$을 구하는 조합 공식은 아래와 같다. 위의 공식으로 팩토리얼 값을 계산하여 풀이할 수도 있지만, 이 문제는 조합의 성질을 이용해 점화식을 만들고 dp로 풀이할 수 있다. 위의 두 가지 성질을 이용해 점화식을 세울 수 있고, 이 성질들은 파스칼 삼각형으로 ..

문제 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 Pair 타입의 list를 만들고 입력받은 정보를 저장한다. 그리고 그 리스트에 sortWith 함수를 이용해 나이 순으로 정렬해준다. sortWith 함수는 자신이 원하는 정렬 규칙으로 Comparator를 지정할 수 있는 것이다. 이 문제에서는 다른 객체와 나이를 비교하게 하면 된다. 코드 import java.util.* fun main() { val br = System.`in`.bufferedReader() val bw = System.out.buf..