작심 24/7

7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 처음엔 1부터 M까지 메모리를 기준으로 비용을 구하려 했는데 시간 초과가 눈에 뻔해서 다른 방법으로 바꾸었다. 0부터 최댓값(모든 비용을 다 더한 값)까지 비용을 기준으로 배낭 채우기 방식을 이용하여 최대 메모리를 dp배열에 채워 넣는다. 최종 배열에서 가장 먼저 M이상인 값이 나온 인덱스를 출력하면 그게 바로 최소 비용이다. #include #include using namespace std; int N, M, cnt, mem[101], cost[101], dp[..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 무게들과 그에 따른 가치들을 pair로 벡터에 넣고 오름차순으로 정렬한다. 이차원 배열 DP를 만들어 0/1 Knapsack 원리로 구현한다. 평범한 배낭과 동전 문제와 비슷한 개념인데 차이점은 동전은 같은 동전을 여러 개 쓸 수 있다는 것이고 평범한 배낭은 이 물건을 가져가거나, 가져가지 않거나. 이 두가지 선택지밖에 없다는 것이다. 그래서 문제에 있는 예제로 표를 채워보면 가치 무게 1 ..