dp

✨ 자바로 푸는 가장 긴 감소하는 부분 수열 문제 풀이 📌 문제 개요 수열이 하나 주어졌을 때, 해당 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하는 문제입니다. 예를 들어, 수열이 10 30 10 20 20 10이라면가장 긴 감소하는 부분 수열은 30 20 10 → 길이 3 👉 이 문제는 **Longest Decreasing Subsequence (LDS)**를 찾는 전형적인 DP 문제입니다. 💡 예제 입력6 10 30 10 20 20 10 💡 예제 출력3 🛠 알고리즘 접근 방식 **가장 긴 증가하는 부분 수열(LIS)**과 동일한 접근 방식이며,조건만 arr[j] > arr[i]로 바뀝니다. 🔸 DP 정의 dp[i]: i번째 원소를 마지막으로 하는 가장 긴 감소 수열의 길이 ..

✨ 자바로 푸는 가장 큰 증가하는 부분 수열 문제 풀이 📌 문제 개요 “가장 큰 증가하는 부분 수열” 문제는 다음과 같은 조건을 만족하는 부분 수열을 찾는 문제입니다. 수열 A에서 증가하는 부분 수열 중, 합이 가장 큰 부분 수열의 합을 구하라! 즉, 단순히 길이가 아니라 합이 최대인 증가 수열을 구하는 문제입니다. 💡 예제 입력10 1 100 2 50 60 3 5 6 7 8 💡 예제 출력113→ 부분 수열: 1 + 2 + 50 + 60 = 113 (또는 1 + 100) 🛠 알고리즘 접근 방식 이 문제는 **DP(동적 계획법)**을 통해 해결할 수 있습니다. 우리는 아래와 같은 배열을 정의합니다. dp[i]: i번째 수를 마지막으로 하는 증가 수열의 최대 합 이후, 앞의 원소들과 비교하며 ..

✨ 자바로 푸는 오르막 수 문제 풀이 📌 문제 개요 오르막 수란, 각 자릿수가 비내림차순(내림하지 않는 순서)으로 구성된 수를 말합니다.예를 들어 1234, 1123, 5555는 오르막 수입니다.321, 201과 같이 감소하는 수가 있는 경우는 오르막 수가 아닙니다. 문제 목표는길이가 N인 오르막 수의 개수를 구하는 것이며,정답은 10007로 나눈 나머지를 출력합니다. 💡 예제 입력1 💡 예제 출력10 🛠 알고리즘 접근 방식 이 문제는 DP(동적 프로그래밍) 을 사용해 해결할 수 있습니다.우리는 다음 조건을 만족하는 점화식을 세울 수 있습니다. dp[i][j] : 길이가 i이고, 마지막 자릿수가 j인 오르막 수의 개수dp[i][j] = dp[i][j+1] + dp[i-1][j]끝자리가 j 이..

https://www.acmicpc.net/problem/11052 ✨ 자바로 푸는 카드 구매하기 문제 풀이 📌 문제 개요 N개의 카드를 구매해야 할 때, 각 카드팩은 카드 개수와 가격이 다르다.카드 N개를 구매하는 최대 금액을 구해야 한다.전형적인 완전 탐색 기반의 DP 최적화 문제. 💡 예제 입력4 1 5 6 7설명:카드 1개짜리 팩은 1원, 2개짜리 팩은 5원, …4개를 구매할 때 최대 금액을 구하는 문제. 🛠 알고리즘 접근 방식 dp[i]는 카드 i개를 구매할 수 있는 최대 비용을 의미.i장을 구매하려면:j장을 먼저 사고, 나머지 i-j장을 다시 구입할 수 있다.즉, dp[i] = max(dp[i], dp[i-j] + price[j]) 이때 모든 j에 대해 반복하면서 최대값 갱신...

https://www.acmicpc.net/problem/2193 ✨ 자바로 푸는 이친수 문제 풀이 📌 문제 개요 백준 2193번 “이친수” 문제는 특별한 조건을 가진 이진수의 개수를 세는 문제입니다. N자리 이친수란?0으로 시작하지 않음1이 두 번 연속으로 나올 수 없음 N자리 이친수가 총 몇 개 있는지 구하는 문제로, **DP(동적 계획법)**을 이용해 해결할 수 있습니다. 💡 예제 입력3 예제 출력2가능한 이친수: 100, 101 🛠 알고리즘 접근 방식 이 문제는 피보나치 수열과 유사한 점화식을 갖습니다. dp[i] = i자리 이친수의 개수N자리 이친수는N-1자리 이친수에 0 추가N-2자리 이친수에 10 추가 단, 연속된 1이 안 되도록 조건이 자연스럽게 반영됩니다. ✅ 핵심 아이..

https://www.acmicpc.net/problem/14501 ✨ 자바로 푸는 퇴사 문제 풀이 📌 문제 개요 백준 14501번 “퇴사” 문제는 퇴사를 앞둔 상담원이 남은 N일 동안 최대한 많은 수익을 올릴 수 있도록 상담 일정을 최적으로 조정하는 DP(동적 계획법) 문제입니다. 각 날짜별로 상담을 진행할 경우 소요되는 일수와 받을 수 있는 보상이 주어지며, 퇴사 전까지 끝나는 상담만 수행할 수 있습니다. 💡 예제 입력73 105 201 101 202 154 402 200 예제 출력45 🛠 알고리즘 접근 방식 dp[i]는 i일에 얻을 수 있는 최대 수익을 의미합니다.각 날짜 i에서 상담을 할 수 있다면, i + days[i]일에 dp[i] + pays[i]를 반영합니다.매일 상담을 하지..

https://www.acmicpc.net/problem/11062 ✨ 자바로 푸는 카드 게임 문제 풀이 📌 문제 개요 백준 11062번 “카드 게임” 문제는양 끝에서 카드를 번갈아 가져가는 두 플레이어가 있을 때, 첫 번째 플레이어가 얻을 수 있는 최대 점수를 계산하는 문제입니다. 이 문제는 두 사람 모두 최선의 선택을 할 때, 나의 점수를 최대화할 수 있는 방법을 찾아야 하므로,전형적인 DP(다이나믹 프로그래밍) 문제입니다. 💡 예제 입력144 7 2 9 ✅ 예제 출력13 🛠 알고리즘 접근 방식 구간 [s, e]에서 플레이어가 차례일 때,최적의 선택을 했을 때 얻을 수 있는 점수를 dp[s][e]로 정의합니다.합계 - 상대방 점수 방식으로 현재 플레이어 점수를 계산합니다.prefix[..

https://www.acmicpc.net/problem/10942 🔁 자바로 푸는 펠린드롬? 문제 풀이 (백준 10942) 📌 문제 개요 수열이 주어졌을 때, 특정 구간이 펠린드롬(회문)인지 빠르게 판별해야 하는 문제입니다.질의가 최대 100만 번까지 주어지므로, 단순한 비교로는 시간 초과가 발생합니다. 💡 예제 입력71 2 1 3 1 2 141 32 53 35 7 예제 출력1 0 1 1 🛠 알고리즘 접근 방식 이 문제는 DP(Dynamic Programming) 을 활용해모든 가능한 구간에 대해 펠린드롬 여부를 미리 계산한 뒤,질의에 대해 빠르게 응답하는 구조로 풀 수 있습니다. ✅ 핵심 아이디어 isAns[s][e] = true if arr[s] == arr[e] and i..

https://www.acmicpc.net/problem/2618 📌 자바(Java)로 푸는 경찰차 - 백준 2618 🚓🚓두 경찰차의 최소 이동 거리 + 이동 경로까지 구하는 DP 문제 🔎 문제 개요 백준 2618 - 경찰차 문제는N × N 크기의 도시에 경찰차 2대가 배치되어 있고,여러 사건이 순차적으로 발생할 때두 경찰차가 어떻게 사건을 분담해서총 이동거리를 최소화할 수 있는지를 구하는 문제입니다. 경찰차 1: 항상 (1,1) 위치에서 시작경찰차 2: 항상 (N,N) 위치에서 시작각 사건은 정확히 한 번만 처리해야 하며,각 사건은 경찰차 1 또는 경찰차 2가 처리해야 합니다.💡 예제 입력633 55 52 3 💡 예제 출력9121 총 이동거리: 9각 사건을 처리한 경찰차 번호 출력 🛠..

https://www.acmicpc.net/problem/14003 📌 자바(Java)로 푸는 가장 긴 증가하는 부분 수열 5 - 백준 14003 🔼LIS + 경로 추적을 O(N log N)으로 해결하는 대표 문제 🔎 문제 개요백준 14003번 - 가장 긴 증가하는 부분 수열 5 문제는수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이해당 부분 수열 자체 를 구하는 문제입니다.단, 수열의 길이가 최대 100만 개이므로 O(N²) 풀이 불가능합니다. 💡 예제 입력610 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 ✅ 핵심 전략: 이진 탐색 기반 LIS + 경로 추적 list[]: 현재까지 만든 LIS 수열 (값만 추적)dp[i]: arr..