ImJay

[BOJ/Java] 9095. 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 해석 이 문제에서는 주어진 정수 𝑛n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 동적 프로그래밍(Dynamic Programming) 문제이다. 예를 들어, 𝑛=4n=4인 경우, 다음과 같이 총 7가지 방법이 있다: 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 풀이 과정 이 문제의 풀이는 각 숫자를 1, 2, 3의 합으로 나타내는 방법의 수를 배열 dp에 저장하는 것을 포함한다. 여기서 dp[i]는 숫자 𝑖i를 나타내는 방법의 수를 저장한다. 초기 값으로 dp[1] = ..

[BOJ/Java] 2579. 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해석 이 문제는 주어진 계단을 오르는 최적의 방법을 찾는 다이나믹 프로그래밍 문제이다. 계단에는 점수가 부여되어 있으며, 한 번에 1개 혹은 2개의 계단을 오를 수 있다. 단, 연속된 세 개의 계단을 모두 밟으면 안 된다. 최종 목적은 계단 꼭대기에 도달할 때 최대 점수를 얻는 것이다. 풀이 과정 제출된 코드는 다이나믹 프로그래밍 방식을 사용하여 각 계단에 도달했을 때의 최대 점수를 계산한다. 코드는 다음과 같은 접근 방식을 ..

[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를 사용하여 각 위치에서 목표 위치까지 도..

[BOJ/Java] 19942. 다이어트 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 문제 해석 다이어트 문제(BOJ 19942)는 주어진 영양소의 최소 요구량을 만족하는 식단을 찾는 문제이다. 각 식단은 단백질, 지방, 탄수화물, 비타민을 포함하며, 주어진 요구량을 만족하는 식단 중 최소 비용을 갖는 식단을 찾는 것이 목표이다. 풀이 과정 이 문제는 부분 집합의 속성을 활용하여 모든 가능한 조합을 탐색하는 방법으로 해결할 수 있다. 재귀적 방법으로 각 음식을 선택하거나 선택하지 않는 모든 경우를 고려하며..

[BOJ/Java] 20055. 컨베이어 벨트 위의 로봇 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 해석 컨베이어 벨트와 로봇의 상호작용을 시뮬레이션하는 본 문제에서는 벨트가 원형으로 연결되어 있으며, 로봇이 올라갈 수 있는 위치와 올라갈 수 없는 위치로 구분되어 있다. 각 칸에는 내구도가 존재하며, 로봇이 칸 위로 이동하거나 벨트가 회전할 때마다 내구도가 감소된다. 주어진 조건 하에서 내구도가 0인 칸의 수가 특정 값(K) 이상이 될 때까지의 반복 과정을 통해 진행 단계 수를 ..

[BOJ/Java] 9935. 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해석 "문자열 폭발" 문제는 주어진 문자열에서 특정 "폭발 문자열"이 있을 경우, 그 문자열을 모두 제거하고, 제거 후 남은 문자열에 다시 폭발 문자열이 포함되어 있다면 이를 반복적으로 제거하는 과정을 거쳐 최종적으로 남은 문자열을 반환하는 문제다. 만약 모든 문자가 제거될 경우 "FRULA"를 출력한다. 이 문제는 특히 문자열 처리와 스택을 활용하는 알고리즘 설계 능력을 요구한다. 풀이 과정 이 문..

[BOJ/Java] 17837. 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 해석 이 문제는 체스판에서 말을 이동시켜서 게임을 진행하는 시뮬레이션 문제다. 체스판의 각 칸은 흰색, 빨간색, 파란색으로 구분되어 있으며, 말은 특정 방향으로만 이동할 수 있다. 말은 다른 말 위에 올라탈 수 있으며, 이동 시 다양한 규칙에 따라 처리가 달라진다. 게임의 목표는 말이 네 개 이상 쌓이면 게임을 종료하는 것이다. 이 문제의 주요 도전은 말의 이동과 위치, 방향 변경 등을 정확히 처리하는 것이..

[BOJ/Java] 9251. LCS (최장 공통 부분 수열) 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 해석 LCS 문제는 두 문자열이 주어졌을 때, 두 문자열 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제이다. 이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 방식을 사용하며, 이를 구현하기 위한 점화식을 개발하고 코드로 옮겨야 한다. 풀이 과정 주어진 코드는 두 문자열 a와 b를 입력 받고, 이를 문자 배열로 변환한..