문제 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 곱셈 공식을 활용한 분할 정복을 수행하는 재귀 함수로 해결하면 된다. (1629번 곱셈 문제와 같다.) 재귀 함수에서는 다음과 같이 지수를 반으로 나눠가며 계산한다. 지수가 1인 경우에 입력받은 행렬을 그대로 리턴하면 된다. - 지수가 짝수인 경우 $a^n = a^{n/2} \times a^{n/2}$ - 지수가 홀수인 경우 $a^n = a^{n/2} \times a^{n/2}\times a$ 행렬의 곱셈은 다음 이미지와 같은 방식으로 처리되며, 3중 for문으로 구..

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 소수 판정을 먼저 수행하고, 투 포인터를 이용하여 합이 입력받은 값이 되는 경우를 세어주면 된다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가며 소수를 구하는 방법이다. 다음의 그림을 보면 쉽게 이해할 수 있다. 먼저 입력받은 범위까지의 소수를 구하고, 그 소수를 리스트에 저장한다. 이 리스트를 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포..

문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 풀이 입력받은 두 자연수의 최대 공약수가 모든 자리가 1로만 이루어져있는 두 자연수의 최대 공약수의 자리수가 된다. 따라서 입력받은 수의 최대 공약수를 구하고 최대 공약수만큼 1을 출력해주면 된다. 예제 입력 2를 보면 3 과 6의 최대 공약수는 3이고 답은 111이다. 11111 = 111 x 1001로 나타낼수 있기 때문에 답은 맞다. 풀이가 왜 성립하는지의 증명은 https://www.acmicpc.net/board/view/32..

문제 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 = ((..