ImJay

[BOJ/Java] 4485. 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해석 이 문제는 다익스트라 알고리즘을 이용하여 최소 비용 경로를 찾는 문제이다. 각 칸에는 비용이 존재하고, 이 비용을 최소화하면서 오른쪽 아래 구석으로 이동해야 한다. 이 문제는 전형적인 그리드 기반의 최단 경로 문제로, 각 점에서 상하좌우 네 방향으로 이동할 수 있다. 풀이 과정 입력받은 그리드 map에 대하여 다익스트라 알고리즘을 적용하여 해결한다. 우선적으로 weight 배..

[BOJ/Java] 11722. 가장 긴 감소하는 부분 수열 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 문제 해석 이 문제는 주어진 배열에서 가장 긴 감소하는 부분 수열의 길이를 찾는 문제이다. 감소하는 부분 수열이란, 수열의 원소들이 감소하는 순서로 정렬된 수열을 의미한다. 풀이 과정 제출된 코드는 동적 프로그래밍(DP)을 이용한 방식으로 구현되어 있지만, 로직에 오류가 있어 정확히 문제의 요구사항을 충족하지 못하는 부분이 있다...

[BOJ/Java] 1520. 내리막 길 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 해석 "내리막 길" 문제는 지정된 MxN 격자에서 각 셀에는 높이가 주어지며, 항상 상하좌우로만 이동할 수 있는 조건에서, 시작점 (M, N)에서 목표점 (1, 1)까지 내리막길로만 이동하는 경로의 수를 구하는 문제이다. 이동은 오직 더 낮은 높이의 셀로만 가능하다. 풀이 과정 이 문제는 동적 프로그래밍(DP)과 깊이 우선 탐색(DFS)을 활용하여 해결할 수 있다. DP 배열 dp를 사용하여 각 위치에서 목표 위치까지 도..