2629_양팔저울(파이썬,쉬운풀이)

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

2629번: 양팔저울

 

 

처음에 문제를 보고 조금 고민을 하다가,

 

추를 한개씩 추가해주면서 구할수 있는 무게를 담은 리스트를 만들면 되지 않을까? 라는 생각을 했다.

 

원래 있던 리스트에 새로 들어온 추를 더하거나, 빼준 값을 추가해주면 쉽게 구할 것 같았다.

 

1    -> [ 0 , 1]

1 ,4    -> [ 0 , 1 , (0+4), (0-4) , (1 + 4 ) , (1 - 4) ]

 

이때 -값은 절대값을 취해주고, 중복되는 값을 없애지 않으면 연산량이 많아질것 같아 없애주는 작업을 취해주었다.

 

 

사실 가면갈수록 연산량이 많아지긴 하나, 테스트케이스가 많지 않아서 적용시켜본 코드이다.

 

n,chu_lst = int(input()),list(map(int,input().split()))
m,check_chu_lst = int(input()),list(map(int,input().split()))

dp = [ 0 ]
for chu in chu_lst:
    tmp=[]
    for i in dp:
        tmp.append(i+chu)
        tmp.append(abs(i-chu))
    dp = list(set((dp + tmp)))

for chu in check_chu_lst:
    print('Y' if chu in dp else 'N',end=' ')

 

 

++ 중간에 테스트하려고 print문을 넣었었는데 이것때문에 계속 답이 틀렸다고 나와서 멘붕에 빠졌었다... 후..