n . n

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 대표적인 0-1 knapsack 문제이다. https://kikikiwiii10.tistory.com/86 knapsack problem 작년.. 이 아니라 재작년 수업 때 배운 건데 완 전 까먹어서 문제 풀 때 써먹지 못했다ㅠ Fractional Knapsack 0-1 Knapsack "배낭 채우기 문제" 로 알려져 있으며 위와 ..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 다이나믹 프로그래밍. 현재 위치를 [row][col]이라고 할 때, 현재 위치에서 가질 수 있는 합은 (왼쪽 상단에서 온 값 or 오른쪽 상단에서 온 값) + 현재 위치의 숫자 이므로 두 값을 비교하여 더 큰 값을 dp[row][col] 위치에 저장하는 식으로 탐색하면 리프 위치에서의 최댓값을 구할 수 있음 public class Solution { public static int solution(int[][] triangle) { in..