[백준 16287번] Parcel (Python3)

def solve():
  check = [0]*(W+1)
  for i in range(N):
    for j in range(i+1,N):
      if (w:=weight[i]+weight[j])<=W:
        check[w] = (i,j)
  for i in range(N):
    for j in range(i+1,N):
      if (w:=weight[i]+weight[j])<=W and check[W-w]:
        if i not in check[W-w] and j not in check[W-w]:
          return 1

W,N = map(int,input().split())
weight = [*map(int,input().split())]
print("YES" if solve() else "NO")

중간에서 만나기 [백준 1208번] 부분수열의 합 2 (Python3) (tistory.com) 로 해결하였다.

오랫동안 풀이방법을 생각해내지 못한 문제였다. 4개를 모두 뽑는것은 시간복잡도상 불가능하므로 2개를 뽑아서 합을 구하는 것을 이용해야한다는 것까지는 짐작할 수 있었는데, 중복체크를 어떤방식으로 해야할지를 떠올리지 못하였다. 그러다가 "모든 무게가 다르다는 것에 주의해야한다" 라는 힌트를 통해 문제를 해결할 수 있었다.

 

풀이를 설명하면,

1. 0~W까지 무게의 check 배열을 만든다.

2. 모든 i,j에 대해 2중 for문을 통해 2개를 뽑아 만들 수 있는 무게를 확인하고, 이를 해당 무게의 check배열에 저장한다. 이때 한쌍만 저장한다.

3. 한번 더 2중 for문을 돌면서 두 무게의 합이 w라면 W-w 무게를 만들 수 있는지 확인하고, 인덱스가 겹치는지 확인하여 겹치지 않으면 YES를 출력한다.

 

모든 무게가 다르기 때문에 2에서 한 쌍만 저장해도 답을 구할 수 있다는 것이 핵심 포인트였다.

 

 

오늘의 교훈) 중간에서 만나기는 유용하다.