백준 2629. 양팔저울

ㅇhttps://www.acmicpc.net/problem/2629

2629번: 양팔저울

 

d[i][j] = i번째 추 까지 사용했을때, j의 무게를 만들수 있다면 true 

 

 

양팔 저울의 왼쪽에 구슬을 놓는다고 하면, 우리는 세가지 행동 중 하나를 할 수 있다.

 

1. 오른쪽에 추를 놓는다.

2. 왼쪽, 즉 구슬 쪽에 추를 놓는다.

3. 추를 놓지 않는다.

 

dfs로 탐색해주면 되는데 구슬 쪽에 추를 놓을때를 조심해야 한다.

구슬쪽에 추를 놓을때 현재 무게 w에서 단순히 추 무게를 빼는게 아니라 절댓값을 씌어 줘야 한다.

예를들어 현재까지 무게가 3인데 무게 5의 추를 왼쪽 즉 구슬 쪽에 놓는다면 abs(3-5) = 2가 되어야 한다.

이 상태에서 반대 쪽에 2짜리 구슬을 놓으면 평행이되기 때문에 무게 2 짜리 구슬도 탐색 가능하기 때문이다.