문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 입력받은 블록 나타내는 2차원 배열을 생성하여 해결하였다. 배열에서 1은 블록을 나타내고 0은 빈 공간을 나타내도록 구성했다. 2중 for문을 사용하여 1층부터 확인한다. 처음 블록을 만나면 해당 블록 다음부터 빈 공간의 개수를 세고, 다시 블록을 만나면 빈 공간에 빗물이 고일수 있는 것으로 처리하여 전체 결과값에 더해준다. 모든 층을 확인하고 결과값을 출력해주면 된다. 코드 fun main() { val br = System.`in`..

문제 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까지만 하면 된다. 팰린드롬의 확인은 수를 문자열로 변환하여 확인하면 된..