문제 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이 문제는 행렬의 거듭제곱을 이용해 피보나치를 구하는 방법으로 해결할 수 있고 구하는 방법은 다음과 같다. 피보나치 수열을 수식으로 나타내면 $f_{n+2} = f_{n+1} + f_{n}$ 이고, 식을 행렬의 곱으로 나타낼 수 있다. $f_{n+2} = f_{n+1} + f_{n} \\ = 1 \times f_{n+1} + 1 \times f_{n} \\ = \begin{bmatrix}1&1\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$ 2 X 2 행렬을 만..

문제 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 백트래킹을 사용하여 해결할 수 있다. 백트래킹은 가능한 모든 경우의 수를 탐색하면서 답을 찾는 알고리즘으로 재귀 함수를 이용한다. 재귀 함수에서는 현재 선택한 재료로 만들어진 음식의 신맛과 쓴맛을 계산하고, 두 맛의 차이의 최소값을 갱신한다. 이후 다음 재료를 선택하고 다시 재귀적으로 함수를 호출한다. 선택한 재료는 방문 처리를 하여 중복 선택을 방지한다. 모든 가능한 조합을 탐색한 후에 최소값을 출력한다. 코드 import ko..

문제 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문으로 구..

문제 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 먼저 에라토스테네스의 체를 이용해 소수 판정을 하고, whlie문을 이용해 입력받은 수보다 큰 팰린드롬 수를 찾으면 된다. 에라토스테네스의 체는 소수의 배수들을 지워가면서 소수를 판정하는 것으로 다음 이미지를 보면 쉽게 이해할 수 있다. 문제에서 주어진 범위 1000000보다 큰 팬린드롬 소수는 1003001이기때문에 소수 판정은 1003001까지만 하면 된다. 팰린드롬의 확인은 수를 문자열로 변환하여 확인하면 된..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다. 반복문으로 해결하면 시간초과가 발생한다. 풀기 위해서는 지수 법칙과 모듈러 연산 성질에 대해 알고 있어야 한다. - 지수 법칙: $a^{(n+m)} = a^n \times a^m$ - 모듈러 연산 곱셈 성질: $(a\times b)\mod c = (a\mod c \times b\mod c)\mod c$ 이 두 성질을 활용하여 재귀 함수를 만들면 된다. 함수는 지수가 1이 될 때까지 B를 절반으로 나누어가며 계산한다. - 지수가 짝수인 경우 $a^n = ..