문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 문제는 하나의 자연수를 1, 2, 3으로 조합하여 만드는 경우의 수를 구하는 것으로 우선 1, 2, 3을 만드는 경우의 수를 먼저 확인해보자. 1을 만드는 경우의 수는 (1)으로 1개고, 2를 만드는 경우의 수는 (1 + 1), (2)로 2개, 3을 만드는 경우의 수는 (1 + 1 + 1), (1 + 2), (2 + 1), (3)으로 4개다. 1, 2, 3을 조합하여 4를 만드는 방법은 (1 + 3), (2 + 2), (3 + 1)로 나타낼 수 있는데, (1 + 3)은 (1) + (1 + 1 + 1), (1) + (1 + 2), (1) + (2 + ..

문제 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로 풀이할 수 있다. 위의 두 가지 성질을 이용해 점화식을 세울 수 있고, 이 성질들은 파스칼 삼각형으로 ..