목록배낭문제 (1)

전자공학 및 알고리즘

백준 2629 - 양팔저울(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 배낭문제를 이용한 Dp 문제입니다. 주어진 추의 무게를 통해 원하는 구슬 무게를 잴 수 있는지 물어보는 문제입니다. 다른 배낭 알고리즘을 이용한 문제와 달리, 이 문제의 특이한 점은 추를 반대편에서 달 수 있다는 점입니다. 따라서, X무게에서 새로운 추를 놓을 때, X+Y or X-Y의 무게를 두개다 잴 수 있습니다. 또한, N개의 추를 이용해 잰다고 해도, 이전에 잴 수 있었던 ..
백준 2023. 1. 20. 15:27
이전 Prev 1 Next 다음