ImJay

[BOJ/Java] 2749. 피보나치 수 3https://www.acmicpc.net/problem/2749문제 해석피보나치 수 3 문제는 \(n\)번째 피보나치 수를 \(1,000,000\)으로 나눈 나머지를 구하는 문제이다. 단, \(n\)은 \(1,000,000,000,000,000,000\)까지 가능하므로, 일반적인 재귀나 반복문으로는 해결할 수 없다. 이 문제는 **피사노 주기(Pisano Period)**를 활용하여 해결할 수 있다.풀이 과정 피사노 주기 이해: 피보나치 수를 \(m\)으로 나눈 나머지는 주기를 가진다. 이 주기를 피사노 주기라고 하며, \(m = 1,000,000\)일 때 피사노 주기는 \(1,500,000\)이다. 피사노 주기 활용: \(n\)을 피사노 주기로 ..

[BOJ/Java] 2933. 미네랄https://www.acmicpc.net/problem/2933🔍 문제 분석백준 2933번 "미네랄" 문제는 2차원 격자 형태의 동굴에서 막대를 던져 미네랄을 부수고, 이후 클러스터(공중에 떠 있는 미네랄 조각들)의 중력을 적용하는 시뮬레이션 문제이다.문제를 단계별로 분석하면 다음과 같다:입력동굴의 크기 R×C (최대 100×100)동굴 내 미네랄('x')과 빈 공간('.') 정보막대를 던지는 횟수 N각 막대를 던지는 높이 정보막대가 부딪히는 미네랄 제거왼쪽에서 던지는 경우는 왼쪽부터 탐색하며 'x'를 제거오른쪽에서 던지는 경우는 오른쪽부터 탐색하며 'x'를 제거클러스터 검출 및 중력 적용미네랄이 부서진 후, 공중에 떠 있는 클러스터를 찾아 중력을 적용한다.BFS/..

[BOJ/Java] 10830. 행렬 제곱https://www.acmicpc.net/problem/10830문제 해석행렬 제곱 문제는 주어진 정사각 행렬 \(A\)를 \(B\)번 거듭제곱한 결과를 구하는 문제이다. 단, 각 원소는 \(1,000\)으로 나눈 나머지를 출력해야 한다. 이 문제는 행렬의 거듭제곱을 효율적으로 계산하기 위해 **분할 정복(Divide and Conquer)**과 **행렬 곱셈**을 활용해야 한다.풀이 과정 행렬 곱셈 구현: 두 행렬을 곱하는 함수를 구현한다. 이때, 곱셈 결과의 각 원소는 \(1,000\)으로 나눈 나머지를 저장한다. 분할 정복을 이용한 거듭제곱: 행렬 \(A\)를 \(B\)번 거듭제곱할 때, \(B\)가 짝수인 경우와 홀수인 경우로 나누어 재귀적으로..