[백준/16287] Parcel (Python)

Problem : https://www.acmicpc.net/problem/16287

16287번: Parcel

Difficulty : Platinum 5 

 

Status : Solved

 

Time : 01:25:27

 

---

 

문제 설명

 

 

국제대학소포센터(ICPC: International Collegiate Parcel Center)는 전세계 대학생들을 대상으로 소포 무료 배송 이벤트를 진행하고 있다. 무료 배송 조건은 보낼 소포가 물품 4개로 구성되어야 하며 이들 물품의 무게 합이 정확히 정해진 정수 무게 w 그램이어야 한다는 것이다.

부산대학교에 있는 찬수는 영국 왕립대학에 있는 수환에게 보낼 물품이 매우 많이 있는데, 각 물품의 무게(모두 정수 그램)는 모두 다르다. 이 이벤트는 한시적으로 진행되는 이벤트이기 때문에 찬수는 자신이 보낼 물품 중에서 이 조건을 만족하는 물품 4개가 있는지 가능하면 빨리 알아내고 싶다. 다시 말해서 서로 다른 n(n ≥ 4)개의 정수로 이루어진 집합 A에서 4개의 원소만 꺼내어 만든 부분집합 B(|B| = 4)가 ∑b∈B b = w 조건을 만족하는지 판단하려고 한다. 

주어진 w와 A에 대해서, 위 조건을 만족하는 부분집합 B가 존재하면 YES를, 아니면 NO를 출력하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 공백으로 분리되어 주어진다. 각 원소 ai는 1이상 200,000이하이다(1 ≤ ai ≤ 200,000).

 

출력

 

출력은 표준출력을 사용한다. 문제의 조건에 따라 YES나 NO를 한 줄에 출력한다.

 

입력 예시

 

10 6
5 10 7 3 2 1

 

출력 예시

 

NO

 

 

---

 

풀이

 

머리 깨지는 줄 알았다... n <= 5000이므로 완전 탐색(n^2)은 무조건 시간 초과, 따라서 중간에서 만나는 방식을 사용하여 O(n^2)의 시간복잡도로 풀어야 된다.

 

서로 다른 수 i, j, k, l를 뽑는다면, (i+j), (k+l)로 나누어 풀어야 한다. 즉 visited 배열에 모든 2가지 조합의 경우의 수를 저장한다고 가정하면, (i+j)와 w - (i + j) 모두를 방문한 경우에 조합이 가능하다고 볼 수 있다. 문제는 (i + j), (w - (i + j)) 이 중복해서 원소를 가지는 경우를 고려할 수 없다는 점이다. 이를테면 i, j, k = 1, 2, 3인 경우를 예로 들어 보자. (i + j) = 3이고 (i + k) = 4이다. 만약 w = 7이라면, w - (i + j) 역시 방문했으므로 가능하다고 출력해버린다(i가 두 번 쓰였으므로 배제해야 함에도 말이다!)

 

이 부분에 대해 오래 고민하다가, 결국 구글링의 힘을 빌려버렸다.

 

https://riyuna.tistory.com/19

[ACM-ICPC 예선, BOJ 16287] Parcel (3)

 

visited 배열을 True/False로 체크하는 것을 넘어서, 조합을 저장하는 게 핵심이다. 만약 w - (i + j) 케이스 검사 시 visited[w - (i + j)]배열이 i 혹은 j를 포함하고 있다면 정답이 될 수 없다. 하지만 문제를 보면 "각 물품의 무게는 모두 다르다"는 조건이 붙어 있다. 즉 만약 a + b = w - (i + j)를 만족하는 다른 쌍 (a, b)이 존재한다면 (i, j)와도 전혀 겹치지 않음이 보장된다. 즉 이 경우는 하나의 쌍을 저장하면 O(N^2)의 시간복잡도 이내에 풀이할 수 있다.

 

풀이 코드 (pypy3)

import sys
input = sys.stdin.readline
w, n = map(int, input().split())
n_list = sorted(list(map(int, input().split())))
visited = [0]*(w+1)

def solve() :
  for i in range(len(n_list) + 1) :
    for j in range(i + 1, len(n_list)) :
      val = n_list[i] + n_list[j]
      if val > w :
        break
      visited[val] = (i, j)
  
  for i in range(len(n_list) + 1) :
    for j in range(i + 1, len(n_list)) :
      val = n_list[i] + n_list[j]
      if val > w :
        break
      if visited[w-val] and i not in visited[w-val] and j not in visited[w-val] :
        return True
  return False

print("YES" if solve() else "NO")

풀이 완료

p.s. DP로도 풀 수 있다는데, 어떻게 풀이하는걸까...?