11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net IDEA 이항 계수를 구하는 문제다. 간단한 다음 공식을 사용하면 바로 해결 가능하다. 그런데 여기서 간단하지 않은 것은 주어진 N의 최댓값이 1,000이다. 20!만 계산해도 long의 표현 범위를 넘어가버린다. 그래서 이 문제에도 분할 정복을 사용해야한다. 그리고 값을 10,007로 나눈 나머지를 출력해야한다. 연산을 모두 끝내고 한꺼번에 나머지를 출력하기엔 너무 큰 숫자를 처리하기 어려울 것 같다. 모듈러 연산을 이용하면 좋겠지만 나눗셈에 대한 모듈러 연산은 없다. 페르마의 소정리에 따르면 어떤 수 a가 정수이고 p가 소수일 때..

18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net IDEA 현재 위치에서 1~N까지의 범위 안에 자유롭게 이동이 가능하다. 브루트포스로 작성하는 것도 가능하겠지만 기상청 컴퓨터를 빌려써야 할 것 같다. N개의 징검다리가 있을 때, N이 1이라면 출발점과 도착점이 같은 것이기 때문에 경우의 수는 1이고 2 이상일 때부터 출발점과 도착점 사이의 징검다리들을 각각 밟을 것인지 건너 뛸 것인지 선택하는 것과 같다. N - 2 개의 징검다리 중 1개만 밟는 경우, 2개만 밟는 경우, 3개만 밟는 경우, ..., N - 3 개를 밟는 경우, N - 2개를 모두 밟는 경우를..