ImJay

[BOJ/Java] 1463. 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석 이 문제는 주어진 수 𝑋X를 1로 만드는 데 필요한 최소 연산 횟수를 찾는다. 연산은 다음 세 가지 중 하나를 선택할 수 있다: 𝑋X가 3으로 나누어 떨어지면, 3으로 나눈다. 𝑋X가 2로 나누어 떨어지면, 2로 나눈다. 𝑋X에서 1을 뺀다. 풀이 과정 이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있다. 각 숫자 𝑖i에 대하여, 𝑖i를 1로 만드는 최소 연산 횟수를 dp[i] 배열에 저장한다. 점화식은 다음과 같다: 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+1 𝑑𝑝[𝑖]=min⁡(𝑑𝑝[𝑖],𝑑𝑝..

[BOJ/Java] 1753. 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해석 이 문제는 주어진 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 고전적인 다익스트라 알고리즘 문제다. 주어진 그래프는 방향성이 있으며, 각 간선에는 가중치가 존재한다. 풀이 과정 제출된 코드는 다음 단계로 문제를 해결한다: 입력 받기: 각 간선 정보를 입력받아 인접 리스트에 저장한다. 다익스트라 알고리즘 실행: 우선순위 큐를 사용하여 현재 정점에서 가장 ..

[BOJ/Java] 11562. 백양로 브레이크 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해석 이 문제는 학교의 건물 간 통행로를 양방향으로 통행할 수 있게 만드는 데 필요한 최소 비용을 계산하는 문제이다. 각 통행로는 일방통행 또는 양방향 통행이 가능하며, 일방통행로를 양방향으로 바꾸는 데에는 비용이 든다. 풀이 과정 제출된 코드는 플로이드-와샬 알고리즘을 사용하여 모든 쌍 최단 경로를 계산한다. 각 건물 간의 최소 비용을 담은 그래프에서, 일방통행로의 경우 양방향으로 변경할 때 추가 비용을 고..