백준 16287번: Parcel (Meet in the middle)

문제링크:16287번: Parcel (acmicpc.net)

16287번: Parcel

이 문제는 5000개의 중복되지 않는 무게를 가진 원소를 4개 골라서 총 합이 w무게로 맞출 수 있는 지 없는지를 구하는 문제이다. 만약 그냥 계산한다면 시간복잡도가 5000C4로 약 O(N^4) = 5000^4로 매우 커질 것이다. 이 문제는 반드시 꼭 4개를 고르는 것에 초점을 두어 2개, 2개로 나누어 두는 경우를 생각하여 중간에서 만나기 알고리즘과 투포인터를 비슷하게 사용해 풀어 시간 복잡도를 O(N^2)로 줄일 수 있었다.

import sys

w,n=map(int,sys.stdin.readline().rstrip().split())

nums=sorted(list(map(int,sys.stdin.readline().rstrip().split())))

visited=[0 for _ in range(800001)]
for i in range(2,n-1):
    leftl=0
    leftr=i-1
    findans=0
    while leftl<i-1:
        leftw=nums[leftl]+nums[leftr]
        if leftw>=w:
            break
        visited[leftw]=1
        leftl+=1
            
    rightl=i
    rightr=i+1
    while rightr<n:
        rightw=nums[rightl]+nums[rightr]
        if rightw>=w:
            break
        if visited[w-rightw]==1:
            findans=1
            break
        rightr+=1

    if findans==1:
        print('YES')
        break

if findans==0:
    print('NO')

만약 2개, 2개로 나누어서 고를 범위를 설정해야 하는데, i를 right의 범위로 잡고 0~i-1을 left으로 잡았다. 범위 내에서 leftr 과 rightl 은 매번 갱신되므로 leftl은 0부터 leftr 전까지, rightr은 rightl+1부터 n-1까지 조합해 가며 확인한다. 조합 시 처음에 nums를 sort해줬으므로 만약 2개의 조합이 w보다 큰 값이 나온다면, 그 뒤의 값들은 더 커질 것이기에 break 해준다.

 

범위 내에서 leftl과 leftr 중 leftr은 i-1로 고정하고 leftl만 +=1 해주는 이유는 이렇게 하면 만약 i가 2라면 (0,1) i가 3이라면 (0,2) (1,2) 이렇게 조합할 수 있다. i가 3인 경우의 총 조합은 (0,1) (0,2) (1,2) 이렇게 3가지인데, 위 과정을 사용하면 i가 2일때 이미 계산한 것을 visited에 저장 해 주면 중복해서 계산하는 시간 낭비를 줄일 수 있다. 

 

같은 원리로 rightl은 i로 고정하고 rightr만 +=1 해주며 조합하며 경우를 따져간다. i가 2라면 (2,3) (2,4) (2,5)..(2,n-1) 이렇게 될 것이고 i가 3이라면 (3,4) (3,5) ..(3,n-1) 이렇게 될 것이다. 만약 i가 n-2까지 진행된 경우라면 right의 모든 경우를 조사한 것이 된다.

 

만약 이렇게 left범위의 2개 고른 조합의 값을 누적하여 visited[]에 저장하면 2개, 2개의 범위를 나눠주는 i의 값이 계속해서 증가하며 변화하기 때문에 left와 right의 조합의 인덱스가 겹치는 경우가 있지 않을까? 생각해 볼 수 있지만 그럴 수 없다. 왜냐하면 같은 i기준 right를 조사하는 시점이 i기준 left범위 조합 경우를 visited에 채워준 직후에 하기 때문이다. 만약 left의 i가 2부터 n-2까지 가능한 조합을 모두 채워주고, 그 다음에 right의 가능한 조합을 모두 조사하면 겹치는 경우가 있을 것이다. left와 right를 나누어 가며 중복을 제외 할 경우를 생각하는 것이 어려운 문제였다.