CHAECHAE

https://www.acmicpc.net/problem/12865백준 12865 평범한 배낭 – 1차원 DP 풀이 (Java) 📌 문제 요약물건 N개가 있고 각 물건은 무게(W)와 가치(V)를 가진다.배낭은 최대 K 무게까지 담을 수 있다.각 물건은 한 번만 선택 가능(0/1 배낭)담을 수 있는 가치의 최댓값을 구한다. 💡 핵심 아이디어이 문제는 전형적인 0/1 knapsack문제이다. [DP 정의]dp[w] = 무게 w까지 담을 수 있을 때 얻을 수 있는 최대 가치 [중요한 포인트]같은 물건을 여러 번 쓰면 안 됨따라서 dp 배열을 역순으로 순회해야 함 ❗ 왜 역순으로 순회해야 할까?만약 정방향(w → k)으로 순회하면, 현재 물건을 여러 번 사용하는 상태가 된다.정방향 ❌ → 무한 배낭역방향 ⭕..

https://www.acmicpc.net/problem/1520 1) 문제 한 줄 요약높이가 적힌 격자에서 항상 더 낮은 칸만으로만 이동하여 (0, 0) → (N -1, M - 1)로 가는 경로의 개수를 구하는 문제 2) 왜 DFS + DP(메모제이션) 인가?이동은 "낮아지는 방향"만 허용 → 사이클이 없는 DAG 구조같은 칸을 여러 경로에서 재방문할 수 있으므로 단순 DFS는 중복 계산으로 TLE따라서 (x, y)에서 도착점까지 경로 수를 dp[x][y]에 캐싱(메모제이션)해야 함. 3) 점화식 (핵심 아이디어)정의 : dp[x][y] = (x, y)에서 (n - 1, m - 1)까지 갈 수 있는 경로 수기저 : (x, y)가 도착점이면 dp[x][y] = 1점화식 : dp[x][y] = Σ dp[n..