배낭문제3 [백준/C,C++] 7579번: 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 해당 문제에서 앱의 개수는 100개 이하이고, 확보해야하는 메모리는 10,000,000바이트 이하입니다. 100 x 10,000,000 는 10억으로 너무 크기 때문에, 비활성화 했을 경우의 최대 비용인 100을 사용해 DP 점화식을 짜야합니다. DP[i]를 i의 비용이 주어졌을때 확보할 수 있는 최대 메모리라고 가정해봅시다. 5 60 30 10 20 35 40 3 0 3 5 4 의 예제로 보겠습니.. 2021. 7. 5. [백준/C,C++] 2629번: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 플이 티스토리 꾸준함님의 풀이를 참고하여 풀었습니다. 추를 구슬이 없는 쪽에 올릴지, 구슬이 있는 쪽에 올릴지, 아무 곳에도 올리지 않을지 3가지의 경우를 재귀 호출하며 풀 수 있는 문제입니다. 두번째 예제인 4 2 3 3 3 3 1 4 10 으로 예를 들어보겠습니다. 2, 3, 3, 3의 추 중에 두번째 추까지를 올린다고 해봅시다. 빨간색의 경우 추를 구슬이 없는 쪽에 올리는 경우, 흰색의 경우 .. 2021. 7. 5. [백준/C,C++] 12865번: 평범한 배낭 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 예제 입력으로 바로 설명드리겠습니다. 물건의 수는 4이고, 버틸 수 있는 무게는 7입니다. 각 물건의 무게와 가치는 6/13, 4/8, 3/6, 5/12 입니다. 배낭 무게 1 배낭 무게 2 배낭 무게 3 배낭 무게 4 배낭 무게 5 배낭 무게 6 배낭 무게 7 물건1 (6/13) 0 0 0 0 0 13 13 물건2 (4/8) 0 0 0 8 8 .. 2021. 3. 8. 이전 1 다음
