[Python]알고리즘/백준
[다이나믹 프로그래밍] ★★ 2629번 - 양팔 저울
[백준] 2629번 - 양팔 저울 (한줄평) 생각보다 머리가 복잡했던 문제.. 점화식을 만들기가 어려웠다.. 무조건 복습필수다 풀이 시간: 90분 이내 1) 문제 해결 아이디어 추의 개수 n(30 이하), n개의 추의 무게(500이하의 자연수)가 오름차순으로 주어지고 구슬의 개수 m(7이하), m개의 구슬의 무게(40000 이하의 자연수)가 주어진다. 양팔 저울에 추를 사용하여(올리거나 올리지 않을 수 있음) 주어진 m개의 각 구슬의 무게를 확인할 수 있는지 여부를 구하는 문제다. 각 추를 사용할 때 3가지 경우의 수가 있다. 즉, 추의 개수가 n이면 추를 이용하여 구할 수 있는 모든 경우의 수는 3**n이 된다. n의 값이 최대 30이므로 단순하게 완전 탐색을 한다면 이 문제는 시간초과로 풀 수 없게된..
