[Baekjoon Online Judge] 백준 16287번 Parcel(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 16287번 Parcel

(Python)

(글쓴날 : 2020.05.13)

 

---

* Baekjoon Online Judge, 백준 16287번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 16287번 Parcel

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/16287

16287번: Parcel

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

무게가 각각 다른 물품들이 n개만큼 주어지고, 그중 4개의 물품을 골라 만약, 물품의 합이 정해진 무게 w와 일치하는 경우가 있다면 YES를, 없다면 NO를 출력하는 문제입니다.

 

저의 경우, C++을 사용해 효율이 좋지 않은 코드로 겨우 통과한 뒤, cubelover님의 풀이를 참고하여 Python을 사용해 해결했습니다.

(차후에 만약 문제가 된다면 게시물 삭제 조치하겠습니다.)

처음 C++를 사용해 풀었을 때는 4개의 합을 구하는 문제를 2개의 합을 구하는 문제로 바꾸어, 사전에 모든 물품들을 2개씩 더한 값과 더했던 인덱스들을 저장하고 있는 벡터를 만들어 놓은 뒤, 투 포인터를 적용하여 해결했습니다.

그러나, Python을 사용할 시 위와 동일한 로직으로 접근할 경우 메모리 초과가 발생하였고, 다른 방법을 고민하다 cubelover님의 풀이를 참고해 만약, 두 개의 합이 w 보다 작을 때 준비해둔 배열에 표시를 하여 w - 해당 값이 다른 두 개의 합에서 나올 경우를 찾는 식으로 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
w, n = map(int, input().split())
A = list(map(int, input().split()))
memoization = [False] * w
 
for i in range(n):
    for j in range(i + 1, n):
        if A[i] + A[j] < w and memoization[w - A[i] - A[j]]:
            print("YES")
            sys.exit(0)
    
    for j in range(i):
        if A[i] + A[j] < w:
            memoization[A[i] + A[j]] = True
 
print("NO")

---