글 읽기 - [python] 자꾸 1%에서 틀렸다고 뜹니다

qwer15417 2년 전 0

여러 테스트 케이스를 넣어도 다 맞고, 브루트포스나 탐색에 오류가 있나 해서 테스트를 해봐도 다 맞는 것 같은데 어떤 부분이 오류가 있는지 설명 부탁드립니다 고수님들!

import bisect
import sys

n, c = map(int, sys.stdin.readline().split())
weights = list(map(int, sys.stdin.readline().split()))

# Meet in the middle
a_weights = weights[:n // 2]
b_weights = weights[n // 2:]

a_sums = []
b_sums = []


def a_brute_force(index, temp_sum):
    if temp_sum > c:
        return
    if index == len(a_weights):
        a_sums.append(temp_sum)
        return
    a_brute_force(index + 1, temp_sum)
    a_brute_force(index + 1, temp_sum + a_weights[index])


def b_brute_force(index, temp_sum):
    if temp_sum > c:
        return
    if index == len(b_weights):
        b_sums.append(temp_sum)
        return
    b_brute_force(index + 1, temp_sum)
    b_brute_force(index + 1, temp_sum + b_weights[index])


# 정렬된 sums에서 value보다 작거나 같은 것들의 갯수 출력
def search(sums, value):
    index = bisect.bisect_left(sums, value)
    if index < len(sums) and sums[index] is not value:
        return index
    elif index == len(sums):
        return index
    else:
        return index + 1


a_brute_force(0, 0)
b_brute_force(0, 0)

count = 0
# a_sum과 b_sum의 합이 c보다 작으면 count
b_sums.sort()
for a_sum in a_sums:
    if c - a_sum < 0:
        continue
    count += search(b_sums, c - a_sum)

print(count)

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

문제

문제

출처

ICPC

[python] 자꾸 1%에서 틀렸다고 뜹니다

qwer15417 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말