백준 2629번 양팔저울

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : 구현

(0) 생각

 임의의 무게 W 를 만들 때 모든 추들은 

    1. 쓰이지 않는경우

    2. + 로 쓰이는 경우

    3. - 로 쓰이는 경우

 3중 하나입니다.

 

 문제의 예를 들어 1, 4 의 추가 있다고 하고 모든 가능한 무게를 생각해보면,

무게 \ 숫자	1	4
1	+
3	-	+
4		+
5	+	+

 위와 같이 됩니다.

(1) 코드 7

 따라서 만들어지는 모든 숫자를 저장할 set을 하나 만듭니다.

(2) 코드 14~23

 set에는 0 을 넣어 놓고 시작합니다.

 모든 추를 둘러 보면서 이전에 만들고 set에 저장해 놓은 무게들에 대해 

    1. 더해서 새로운 무게를 만든다.

    2. 빼서 새로운 무게를 만든다.

 를 실행합니다.

 위의 예를 생각해보면, 아래와 같이 진행 되겠죠. 

현재 보는 추	Set에 추가된 숫자
시작	0
1	0, 1, -1
4	0, 1, -1, 4, -4, 5, -3, 3, -5

(3) 주의

 과정 (2)에서, 각 탐색 시 새로 만들어 지는 무게를 따로 저장해 놨다가 set에 추가해야 합니다.

 바로 추가할 경우 set에 추가된 수로 또 만들고 또 만들고... 할꺼에요...