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

ICPC 예선 문제 업솔브를 하려고 보니, 분명 풀었을 터인 Parcel이 재채점으로 인해서 틀렸습니다로 바뀌어 있는 처참한 상황을 보게 되었다.(이 문제에 얽힌 이야기는 이전 포스트 Parcel 1과 2를 참조)

 

어디서 틀렸나 열심히 찾아봤는데....생각보다 엉뚱한 곳이었다. 코드를 봤을 때 A+A+B+B꼴을 체크할 때, sums는 "합들을 모은 리스트"가 아니고 "합이 존재할 때, 그 n번째 칸에 그 합을 가지는 쌍이 몇개 있는지를 알려주는 리스트"였기 때문에 for문을 작성할 때 실수가 있었고, 그럼에도 불구하고 이전 코드가 맞았습니다가 떴었던 것이다.

 

이 부분을 수정해주고, 그외에 기타등등 소소한 수정을 해주고 다시 맞았습니다를 받을 수 있었다. 로직이 안 틀려서 다행이었다.

 

w,n=map(int,input().split())
L=list(map(int,input().split()))
L.sort()
sums=[0]*400001
for i in range(n):
    for j in range(i+1,n):
        sums[L[i]+L[j]]+=1
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 range(400001):
    if 0<w-i<400001:
        if sums[i] and sums[w-i]:
            count+=sums[i]*sums[w-i]
            if i==w-i:count+=sums[i]*sums[w-i]
count//=2
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//2!=L[i] and a//2!=L[j]:
            count-=1
for i in range(400001):
    if sums[i]:
        if i*2==w:
            count-=1
print(['NO','YES'][count>0])