글 읽기 - 30% 가량에서 틀렸다고 합니다.

ushape 2년 전 0

과연 어떠한 케이스에서 발목이 잡힌 것인지, 논리 상에서 어디에 문제가 생겼던 건지 궁금합니다.

from sys import stdin
def find(n,s):
    # find the the largest number in s which is smaller than n
    start=0; end = len(s)-1
    if s[0]>n: return -1
    while(start<end):
        if end-start==1:
            return end if s[end]<=n else start
        mid = (start+end)//2
        if s[mid]==n: return mid
        if s[mid]<n: start=mid
        else: end = mid
    return end if s[end]<=n else start

def get_comb(last,acc,w):
    # get all possible combinations of weights
    if last>=len(w)-1:
        return [acc,acc+w[last]]
    return get_comb(last+1,acc,w)+get_comb(last+1,acc+w[last],w)

input = stdin.readline
n,c=map(int, input().split())
w=list(map(int, input().split()))
# seperate the given objects into the two groups
# and get all posible combinations for each group
comb1 = get_comb(0,0,w[:n//2]) if n>1 else [0]
comb2 = get_comb(0,0,w[n//2:])
comb2.sort()

# meet-in-the-middle algorithm
ans = 0
for i in comb1:
    ans += 1 + find(c-i, comb2)
print(ans if n else 0)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

30% 가량에서 틀렸다고 합니다.

ushape 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말