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

어제 이 문제를 해결하고 가만 생각해보니, 아무래도 더 빠른 방법이 있을 것 같다는 생각을 지울 수가 없었다.

 

거기에, 결국 ICPC는 C++로 짜야 할텐데, C++로 짜는 방법도 생각해봐야 하지 않겠나는 생각을 했다.

 

더 빠른 방법은 사실 생각해보면 꽤 빠르게 나왔다. 처음에 두개의 합으로 된 리스트를 만들 때, 원소들을 추가하는 방식이 아니라 미리 길이 40만짜리 리스트에다가 1씩 추가하는 식으로 구현하면 O(n^2)만에도 풀 수 있었을 것 같다.(게다가 이 방법이 C++로 구현하는 데에도 조금 더 도움이 될 것 같다!)

 

이 생각을 하고 코드를 조금 수정해보았다.(Python)

 

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]
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:count-=1
print(['NO','YES'][count>0])

sums 리스트를 길이 40만짜리로 바꾸고 그냥 그 합이 몇개 나오는지에 따라서 숫자를 1씩 늘려주는 식으로 했다.

 

(여담인데, 저거 쓰다가 맨 마지막부분 오타가 있는 걸 발견했다. 치명적인 오타였는데 정답에 지장이 안 가서 되게 의아했는데 ,나중에 생각해보니까 뒤에서 세번째 줄부터 시작하는 for i in sums: 부분은 없어도 문제 풀이에 문제가 없는 것 같았다. 저 경우는 이미 앞에서 빠졌기 때문인 거 같다. 저거 아예 지워도 별 문제 없더라.)

 

결과는 이전 코드보다 소요시간이 6배 가량 짧았다.

그건 그렇고, 이걸 내가 언제까지 파이썬만 붙잡고 있을 수는 없는 노릇이다.

 

그래서 C++로도 구현을 해보려고 한다.

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int L[5010];
int sum[400010]={0};
int w, n;
int main(){
    scanf("%d %d", &w, &n);
    for(int i=0;i<n;i++){
        scanf("%d", &L[i]);
        }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            sum[L[i]+L[j]]++;
        }
    }
    int count=0;
    for(int i=0;i<400001;i++){
        if(i<w&&w-i<400001){
            if(sum[i]&&sum[w-i])count+=sum[i];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int a;
            a=w-L[i]-L[j];
            if(a%2==0&&a!=L[i]&&a!=L[j]){
                for(int k=0;k<n;k++){
                    if(L[k]==a/2)count-=2;
                }
            }
        }
    }

    if(count){
        cout<<"YES";
        }
    else{
        cout<<"NO";
        }
    return 0;
}

잘 안 된다. 시간 초과 에러가 뜨고, 게다가 예제도 틀린다.

그래서 다른 아는 후배에게 조언을 구해봤다.

https://en.cppreference.com/w/cpp/algorithm/binary_search

std::binary_search - cppreference.com

stl에 이분탐색을 지원하는 함수가 있었다. 역시 이런 건 찾아봐야 안다.

 

그래서 이를 이용해서 다시 프로그래밍을 해보기로 했다.

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
int L[5010];
int sum[400010]={0};
int w, n;
int main(){
    scanf("%d %d", &w, &n);
    for(int i=0;i<n;i++){
        scanf("%d", &L[i]);
        }
    sort(L,L+n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            sum[L[i]+L[j]]++;
        }
    }
    int count=0;
    for(int i=0;i<400001;i++){
        if(i<w&&w-i<400001){
            if(sum[i]&&sum[w-i])count+=sum[i];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int a;
            a=w-L[i]-L[j];
            if(a%2==0&&binary_search(L,L+n,a/2)&&a!=L[i]&&a!=L[j]){
                count-=2;
            }
        }
    }

    if(count>0){
        cout<<"YES";
        }
    else{
        cout<<"NO";
        }
    return 0;
}

결국 C++로 푸는 데에 성공했고, 속도가 Pypy3보다도 5배쯤 빠른 걸 알 수 있었다.

 

결론: C++을 연습하자