2629번: 양팔저울 www.acmicpc.net 이 문제는 여러 가지 추들을 이용해 주어진 구슬의 무게를 확인할 수 있는지 결정하는 문제로, 단순히 모든 추에 대해 추를 저울 위에 올리지 않거나, 왼쪽 저울에 올리거나, 오른쪽 저울에 올리는 경우로 나눠 계산하는 경우 추의 개수가 n일 때 O(3^n)의 시간 복잡도를 가지므로, brute force로 계산하는 것은 매우 오래 걸린다. 그래서 이 문제는 다른 방법으로 풀어야 하는데, 바로 dynamic programming을 이용해 해결한다. 우선 처음에 생각한 방법은 최대 확인 가능한 구슬의 무게가 40000이므로 길이가 40001인 배열 dp를 만들어 추를 하나씩 추가하면서 확인 가능한 구슬의 무게에 해당하는 인덱스의 값을 1로 하는 방법이었다. 추를..
