글 읽기 - 100% 에서 틀리는데 이유를 모르겠습니다.

kckc0608 7달 전 0

조금 무식하게 케이스를 분류해서 풀고자 했습니다.

양수만 넣는 케이스, 음수만 넣는 케이스, 양수1개 음수 2개, 양수2개 음수 1개

양수와 음수가 섞이는 경우, 2개가 들어가는 것 중 하나를 고정시키고 나머지 하나를 lower bound 로 찾았습니다.

이때, lower bound 뿐만 아니라, 그 직전 값도 정답의 후보가 될 수 있다고 생각해 추가로 검사하도록 하였습니다.

(사실상 O(N^2) 으로 2개를 고르고 나머지 1개를 이분탐색으로 찾는 것인데, 검색을 통해 이 알고리즘은 시간초과를 받아야 함을 알게되었습니다.)

그런데 pypy3 로 제출했을 때 TLE 가 아니라 WA 를 받는데 이 풀이의 구멍이 어딘지를 모르겠습니다.

혹시 min_diff 의 값을 너무 작게 잡았나 싶어서 늘려보았지만 여전히 틀리는데 왜 TLE가 아니라 WA를 받는 건지 알 수 있을까요?

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
minus, plus = [], []
if nums[-1] < 0:
    minus = sorted(nums[:], reverse=True)
else:
    for i in range(n):
        if nums[i] > 0:
            minus = sorted(nums[:i], reverse=True)
            plus = nums[i:]
            break

answer_group = []

# case1 : 양수만 있는 경우
if len(plus) >= 3:
    answer_group.append((plus[0], plus[1], plus[2]))

# case2 : 음수만 있는 경우
if len(minus) >= 3:
    answer_group.append((minus[2], minus[1], minus[0]))

# case3 : 음수가 1개 양수가 2개인 경우 (음수를 기준으로, 양수를 하나 고르고 그것보다 큰 나머지 양수에 대해 이분탐색 진행
if minus and len(plus) >= 2:
    min_diff = 99999999999999999
    min_diff_comb = []
    for neg in minus:
        for k in range(len(plus) - 1):
            pos_num1 = plus[k]
            start, end = k + 1, len(plus) - 1
            while start < end:
                mid = (start + end) // 2
                if plus[mid] + pos_num1 >= abs(neg):
                    end = mid
                else:
                    start = mid + 1

            if abs(neg + pos_num1 + plus[end]) < min_diff:
                min_diff = abs(neg + pos_num1 + plus[end])
                min_diff_comb = (neg, pos_num1, plus[end])

            if end > 1 and abs(neg + pos_num1 + plus[end-1]) < min_diff:
                min_diff = abs(neg + pos_num1 + plus[end-1])
                min_diff_comb = (neg, pos_num1, plus[end-1])


    answer_group.append(min_diff_comb)

# case4 : 음수가 2개 양수가 1개인 경우
if plus and len(minus) >= 2:
    min_diff = 99999999999999999
    min_diff_comb = []
    for pos in plus:
        for k in range(len(minus) - 1):
            neg_num1 = minus[k]
            start, end = k + 1, len(minus) - 1
            while start < end:
                mid = (start + end) // 2
                if abs(minus[mid] + neg_num1) >= pos:
                    end = mid
                else:
                    start = mid + 1

            if abs(pos + neg_num1 + minus[end]) < min_diff:
                min_diff = abs(pos + neg_num1 + minus[end])
                min_diff_comb = (minus[end], neg_num1, pos)

            if end > 1 and abs(pos + neg_num1 + minus[end - 1]) < min_diff:
                min_diff = abs(pos + neg_num1 + minus[end - 1])
                min_diff_comb = (minus[end - 1], neg_num1, pos)

    answer_group.append(min_diff_comb)

answer_group.sort(key=lambda x:abs(sum(x)))
print(*sorted(answer_group[0]))

ai4youej 7달 전 1

반례입니다

5
1 2 7 -10 5

kckc0608 7달 전 0

감사합니다! 큰 도움이 되었습니다 :)

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

문제

문제

출처

ICPC

100% 에서 틀리는데 이유를 모르겠습니다.

kckc0608 7달 전 0

ai4youej 7달 전 1

kckc0608 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말