[python] 백준 16287 Parcel

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

 

 

 

문제 해결

• 오직 4개를 쓰며 정확히 w의 무게를 맞추는 방법에 대해서 여러가지 방법을 생각해 볼 수 있다.
  • DP, DFS ...
• 무게가 엄청 클 수 있고 n이 상대적으로 작으므로 n개에서 4개를 고르는 것을 사용한다.
  • 그런데 4개를 고를 때 graph를 사용하여 dp를 만들기는 상당히 부담스럽다. 4차원 공간보다 2개씩 나누어 2차원 DP를 만들고 2차원 + 2차원 계산을 하는 것이 좋을 것이라 생각했다.
  • 하지만 dp[i][j] 의 value 값을 무엇을 쓸지 사실 의미가 크게 없었다. {0, 1}로 하고 (w-i-j )숫자가 나오는 조합을 N개 안에서 또 찾는 것은 시간복잡도가 상당했다.
  • 따라서 dp를 1차원으로 만들어서 확인을 하는 것이 좋은 방법이었다. 
  • 초기에 dp = [[] for _ in range(w+1)]로 stack 리스트를 만들어 dp[A[i]+A[j]].append((i,j))로 tuple을 리스트 안에 넣는 식으로 만들었다.
  • 하지만 그렬경우 메모리초과가 났고 메모리를 줄이는 방법으로는 당연히 A[i]+A[j] = A[k] + A[l] (i,j,k,l 은 모두 다른 인덱스)일 경우 여러개를 넣어서 고려하지 않아도 된다는 것을 깨닫고 dp = [0 for _ in range(w+1)]로 수정해서 해결하였다. 물론 이경우는 시간이 더 걸린다는 단점이 있다.
    • 실제로 pyhton3에서는 시간초과가 떴다. 하지만 pypy3는 통과

 

메모리 초과 코드

import sys
input = sys.stdin.readline

def solve():
    dp = [[] for _ in range(w+1)]
    for i in range(num):
        for j in range(i+1, num):
            if A[i]+A[j] <= w:
                dp[A[i]+A[j]].append((i,j))
    
    for i in range(num):
        for j in range(i+1, num):
            if A[i] + A[j] <= w and len(dp[w-A[i]-A[j]]):
                if i not in dp[w-A[i]-A[j]] and j not in dp[w-A[i]-A[j]]:
                    return 1
if __name__ == "__main__":
    w, num = map(int, input().split())
    A = list(map(int, input().split()))
    print("YES" if solve()==1 else "NO")

 

정답코드

import sys
input = sys.stdin.readline

def solve():
    dp = [0 for _ in range(w+1)]
    for i in range(num):
        for j in range(i+1, num):
            if A[i]+A[j] <= w:
                dp[A[i]+A[j]] = (i,j)
    
    for i in range(num):
        for j in range(i+1, num):
            if A[i] + A[j] <= w and dp[w-A[i]-A[j]]:
                if i not in dp[w-A[i]-A[j]] and j not in dp[w-A[i]-A[j]]:
                    return 1
if __name__ == "__main__":
    w, num = map(int, input().split())
    A = list(map(int, input().split()))
    print("YES" if solve()==1 else "NO")

 

만약 개수가 한정되지 않은 경우라면 중간에서 왼쪽 사이드와 오른쪽 사이드 나눠서 코드를 작성한다.

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

 

https://thought-process-ing.tistory.com/293

[python] 백준 1208 부분수열의 합