[ACM-ICPC 예선, BOJ 16287] Parcel

작년에 ACM-ICPC 대회에 출전했던 적이 있었다. 내가 참가했던 팀은 5개 해결로 전체 80등 언저리로 본선 진출에는 실패했었는데, 올해에 다시 이 대회에 나가려고 생각을 하고 있다.

 

그 과정에서 작년에 제일 고민을 많이 해봤었던(그렇지만 결국 풀지는 못했던)Parcel 문제를 다시 떠올리게 되었고, 1년만에 문제에게 복수를 하러 가보려고 한다.

 

문제는 여기서 볼 수 있다.

 

쉽게 말해서 뒤에 주어진 정수들 중에서 4개 골라서 앞에서 주어진 정수를 합으로 되게 만들 수 있냐는 문제이다.

 

이런 문제에서 흔히 생각할 수 있는 방법은 다음과 같다.

 

1. 완전 탐색. 주어진 거 4개씩 고르는 경우를 다 찾아보면 된다. 구현은 재귀적으로 대충 하면 될 거 같다.

그러나 n이 5000개까지 가능하다. 4개씩 다 고르는 경우는 5000C4, 즉 대략 2.4*10^13정도의 경우의 수를 해봐야 한다. 이건 아무리 생각해도 아니다.

 

2. DP. 해봄직한 생각이다. 보통 이런 문제는 이렇게 풀리는 경우가 많다. 실제로 대회장에서도 생각했던 방법이 이런 방식이다.

 

그러나 최대 주어지는 무게가 대략 80만까지라서, 복잡도가 대략 O(nw), 즉 5000*800000=40억 정도가 되었다. 40억이면 어떻게든 뭐 되지 않을까 하고 시도해봤지만 어림도 없었다.

 

결국 이 문제는 해결하지 못한채로 대회가 끝나 버렸다.

 

대회가 끝난 뒤에 다른 분들에게 힌트를 들었던 게, 우선 두 개의 물건으로 만들 수 있는 질량들의 종류를 미리 구해둔 뒤에 그걸 이용해서 어떻게 하는 풀이를 알게 되었다. 그렇게 하면 대략 O(n^2logn)정도로 끝낼 수 있다는 듯했다.

 

우선 가장 먼저 떠올린 풀이는 다음과 같았다.

 

서로 다른 두 개로 만들 수 있는 질량들의 list를 만든다->정렬한다->이분탐색으로 잘 뒤져서 거기서 두개 뽑아서 w를 만들 수 있는지 확인한다.

 

그대로 구현을 해보았고, 파이썬 코드는 다음과 같았다.

 

w,n=map(int,input().split())
L=list(map(int,input().split()))
sums=[] #두개씩 모은 합들
for i in range(n):
    for j in range(i+1,n):
        sums.append(L[i]+L[j])
sums.sort() #이진 탐색을 위해서 정렬

def binary_search(L, k):
    start=0
    fin=len(L)-1
    while start<=fin:
        mid=int((start+fin)/2)
        if L[mid]==k:
            return mid
        if L[mid]<k:
            start=mid+1
        else:
            fin=mid-1
    return -1
    
#이진탐색을 위한 함수

value=False
for i in sums:
    if binary_search(sums, w-i)>-1:
        value=True
print(['NO','YES'][value])

그러나 잘 되지 않았다. 당장 예시로 있는 test case 하나도 통과를 못했다.

 

왜 그런가 하고 생각을 해봤는데, 큰 실수 하나를 빼먹었다.

 

서로 다른 물건 두 개의 합들의 리스트를 만들어도 결국 그것들 안에서 두개 골랐을 때 그 안에 같은 물건이 있을 수 있다는 점을 간과했던 것이다.

 

예를 들면, 첫번째 테스트 케이스에서는 5 10 7 3 2 1 중 4개를 가지고 10을 못 만들지만, 위와 같이 프로그래밍을 하게 되면 5 2 2 1과 같은 경우로 가능해져 버린다는 이야기이다.

 

이 문제를 어떻게 해결할까 샤워를 하면서 고민을 하다가, 떠오르게 된 아이디어가 '중복을 포함하게 나오는 경우라면 그 경우의 수가 몇번인지 정해져 있는데, 그냥 그만큼 다 빼보고 생각하면 되지 않을까?' 라는 아이디어를 떠올리게 되었다.

 

이 코드의 경우에는 처음 2개를 고를 때는 중복을 허용치 않았기 때문에 가능한 중복의 경우의 수는 크게 AABC꼴과 AABB꼴로 나눌 수 있다. 첫번째는 한 상품이 중복이 되고 나머지 둘은 서로 다른 경우, 두번째는 각각 한번씩 중복이 된 경우이다.

 

첫번째 경우에서는 sums 리스트에서 AB와 AC를 꺼냈을 때 나오고, 두번째는 AB를 꺼냈을 때만 나온다. 따라서 첫번째는 세는 경우에서 두 번 세지고, 두번째는 1번만 세진다.

 

원래 서로 다른 4개를 가져오는 경우는 ABCD라고 보면, 4C2=6번 세지게 된다.

 

사실 문제를 이렇게 풀면 안될 거 같기는 한데, 6번 미만 세진 경우는 모두 배제한다고 가정하고 다시 풀어봤다.

w,n=map(int,input().split())
L=list(map(int,input().split()))
sums=[]
for i in range(n):
    for j in range(i+1,n):
        sums.append(L[i]+L[j])
sums.sort()
def binary_search(L, k):
    start=0
    fin=len(L)-1
    while start<=fin:
        mid=int((start+fin)/2)
        if L[mid]==k:
            return mid
        if L[mid]<k:
            start=mid+1
        else:
            fin=mid-1
    return -1
count=0
for i in sums:
    if binary_search(sums, w-i)>-1:
        count+=1
print(['NO','YES'][count>5])

물론 잘 될 리는 없다.

틀린 이유는 아무래도 다음과 같은 경우가 있어서인 것 같다.

 

1 2 3 5 9 11 15가 있으면

1 1 2 15, 2 3 3 11, 2 5 5 9로 21을 만들 수 있다. 그러면 AABC꼴만으로도 이미 6개가 나와버리는 문제가 생긴다.

 

물론 이 경우에는 1 2 3 15로 21을 만들 수 있으니 실제로도 YES가 나와야겠지만, 실제 test case에서는 그렇지 않은 경우도 포함되어 있을 수 있다.

 

다른 방법을 생각해보자. AABC나 AABB꼴을 우리가 먼저 찾아내면 되지 않을까?

 

AABC의 경우에는, 2개를 뽑아서 BC로보고 AA로 쓸 수 있는 경우가 있는지, 있다면 몇 번 있는지 체크하면 될 것 같다.

 

AABB꼴은 sum에서 두배 해서 w가 나오는지만 확인하면 된다.

 

코드는 다음과 같이 나온다.

w,n=map(int,input().split())
L=list(map(int,input().split()))
L.sort()
sums=[]
for i in range(n):
    for j in range(i+1,n):
        sums.append(L[i]+L[j])
sums.sort()
def binary_search(L, k):
    start=0
    fin=len(L)-1
    while start<=fin:
        mid=int((start+fin)/2)
        if L[mid]==k:
            return mid
        if L[mid]<k:
            start=mid+1
        else:
            fin=mid-1
    return -1
count=0
for i in sums:
    if binary_search(sums, w-i)>-1:
        count+=1
for i in range(n):
    for j in range(i+1, n):
        a=w-(L[i]+L[j])
        if a%2==0 and binary_search(L,a//2)>-1 and a!=L[i] and a!=L[j]:
            count-=2
for i in sums:
    if i*2==w:w-=1
print(['NO','YES'][count>0])

제출은 파이썬은 속도가 느리기 때문에 Pypy3으로 했고, 드디어 정답을 얻어내서 이 문제에게 통쾌한 복수를 할 수 있었다.