ImJay

[BOJ/Java] 9376. 탈옥https://www.acmicpc.net/problem/9376🔍 문제 분석백준 9376번 "탈옥" 문제는 2명의 죄수를 탈출시키기 위한 최단 경로를 찾는 문제이다.벽('*')을 부수면서 이동할 수 있으며, 문의 개수가 최소인 경로를 찾아야 한다.🚀 풀이 과정이 문제는 BFS(너비 우선 탐색) + 다익스트라 유형의 접근을 해야 한다.맵의 바깥쪽에서 시작할 수 있도록 패딩을 추가한다.죄수가 문을 열고 탈출할 수도 있지만, 밖에서 열어주는 경우도 가능하기 때문.BFS를 3번 수행한다.1회차: 바깥에서 BFS 수행 (외부에서 문을 여는 경우 고려)2회차: 첫 번째 죄수의 위치에서 BFS 수행3회차: 두 번째 죄수의 위치에서 BFS 수행각 BFS에서 문의 개수를 누적하여 ..

[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/..