[알고리즘][2][백준_2629][Python3] - 양팔저울

 

---

문제이해

이 문제에서 헷갈릴수 있는 부분은 주어진 추들을 모두 사용할 필요가 없다는 것이다.

예를들어 추가 1g 3g 5g짜리가 있다면, 5g짜리 하나만 사용해서 5g짜리 구슬을 측정할수있다.

 

---

알고리즘 전략

따라서 예를들어 3개의 추(1g, 3g, 7g)를 가지고 있다고 할때, 

첫번째 추(1g)의 경우 세가지 선택권이 있다.

1. 왼쪽저울에 놓는다

2. 오른쪽저울에 놓는다

3. 저울에 아예 올리지 않는다.

 

그리고 각각의 경우에따라 두번째 추(3g)도 역시 세가지 선택권이 있다.

1. 왼쪽저울에 놓는다

2. 오른쪽저울에 놓는다

3. 저울에 아예 올리지 않는다.

 

마지막추도 역시 동일하다

1. 왼쪽저울에 놓는다

2. 오른쪽저울에 놓는다

3. 저울에 아예올리지 않는다.

 

따라서 3^3 만큼의 경우의수가 존재한다.

 

이를 일반화하면 n개의 추가 주어질때 3^n만큼의 경우의 수가 존재한다.

이 문제에서 n = 30까지 이므로 모든 경우의수를 순수하게 다 돌다가는 제한시간 1초를 넘어 하루가 걸릴지도 모른다.

 

여기서 시간을 줄일수 있는 방법은 재귀를 돌면서 중복되는(이미 간적이 있어서 갈필요가 없는) 부분을 체크해서 stop하고 다음으로 넘어가는 방법을 사용하면 된다.

 

그러기 위해서는 어떤상황에서 중복이 발생하는지 알 필요가 있다.

 

 

하나의 예를 보자

n = 9이고

1g 2g 3g 4g 5g 6g 7g 8g 9g 의 추가 있다고 할때

 

# 첫번째 상황

현재까지

왼쪽저울에 1g 2g 3g 을

오른쪽 저울에 4g을 올렸고 

(5g추는 사용하지 않았다)

6g 추를 올리기 전상황이라고 하자

 

# 두번째 상황

현재까지 

왼쪽저울에 4g 을

오른쪽 저울에 2g을 올렸고 

(1g 3g 5g 추는 사용하지 않았다)

6g 추를 올리기 전상황이라고 하자

 

첫번째상황과 두번째 상황 구체적인 상황은 다르다.

먼저 양쪽의 저울의 각각의 무게합도 다르며, 좌,우를 구성하는 추의 구성도 다르다.

하지만 둘은 같은 경우이다.

 

이유는

왼쪽에 100g 오른쪽에 200g의 추가 있다면 측정할수 있는 구슬의 무게는 100g이다

 

왼쪽에 150g 오른쪽에 250g의 추가 있다면 측정할수 있는 구슬의 무게도 역시 100g이다

 

왼쪽 오른쪽 각각 몇g씩 추가 있는지가 중요한것이 아니라 두 무게의 차가 몇인지가 중요하다.

 

또한 그 100g을 이루고 있는 추가 어떤것인지도 중요하지않다.

 

20g + 30g + 50g의 구성이던

10g + 90g의 구성이던 구할수 있는 구슬의 무게가 100g인것은 변함이 없다.

 

따라서 현재까지 왼쪽,오른쪽 저울에 올라간 총 무게의 차값과 현재 몇번째 추를 사용할 차례인지 알면 그 뒤로 더 진행을 해봐야하는지 말아야하는지 알수 있다.

 

#1 #2 두 상황모두

양쪽 저울의 차 = 2g

현재 사용할 추의 순번 = 6번째 추(6g)

따라서 (2,6) 의 경우라고 볼수 있고 한번도 구한적이 없다면(처음이라면) 재귀를 돌면서 가능한 무게종류들을 리스트에 넣어주면되고

이미 구한적이 있다면 stop하고 다음 경우로 넘어가면 된다.

 

 

이제 코드를 보면서 최종적으로 설계를 해보자

def scale(n_list,n,now,left,right,possible):
    new = abs(left-right)
    if(new not in possible):
        possible.append(new)
    if(now == n):
        return 0
    if(answer[now][new] == 0):
        # 저울의 왼쪽에 놓는경우
        scale(n_list,n,now+1,left+n_list[now],right,possible)

        # 저울의 오른쪽에 놓는경우
        scale(n_list,n,now+1,left,right+n_list[now],possible)

        # 저울에 아예 안놓는경우
        scale(n_list,n,now+1,left,right,possible)
        
        answer[now][new] = 1
    
n = int(input(""))
n_list = list(map(int, input().split()))
m = int(input(""))
m_list = list(map(int, input().split()))
possible = []
answer = [[0]*15001 for i in range(n+1)]


scale(n_list,n,0,0,0,possible)
for i in range(0,len(m_list)):
    if(m_list[i] in possible):
        print("Y",end=' ')
    else:
        print("N",end=' ')