[백준/c++] 15724 주지수
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net ✨ 문제 풀이 (1,1)부터 (i, j)까지의 인구수 합을 저장하는 dp 배열을 memo[i][j]라고 하자 위에 그림과 같이 빨간 네모 + 초록색 네모 - 빨간 네모와 초록색 네모가 겹치는 네모 + 그 부분의 인구수 를 계산하면 (i, j)까지의 인구수 누적합이다 이를 점화식으로 세우면 (i, j)의 인구수 + (1,1)부터 (i-1, j)까지의 인구수 합 + (1, 1)부터 (i, j-1)까지의 인..
[백준/c++] 12865 평범한 배낭
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 🗓 knapsack 조합 최적화의 대표적인 문제 유형 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 문제 유형 짐을 쪼갤 수 있을 때 : 무게를 소수로 쪼갤 수 있음, 분할가능 배낭문제(Fract..