글 읽기 - 반례 부탁드리겠습니다.

hws2006 3년 전 0

수열의 길이가 홀수인 경우,

처음 주어진 수열에서 0과 가까운 값을 찾고, 그 값이 0인지, 0이 수열의 제일 마지막인지 등을 통해서, 해당 값을 수열에서 처리(및 제외)하여 수열의 길이를 짝수로 바꿔줍니다.

그리고 수열의 길이가 짝수인 경우,

두 개의 음수는 서로 곱해주고, 양수일 경우 덧셈보다 곱셈이 크다면 곱셈을 하고, 등등 기타 예외 처리를 해줍니다.

이렇게 알고리즘을 구성해보고 질문 게시판의 모든 반례를 시도해봐도 correct output이 나오지만, 실제 제출해보면 14% 정도에서 틀렸습니다가 나옵니다.

혹시 반례 찾는걸 도와주실분들 계실까요?

import sys


def solution():
    get_input = sys.stdin.readline
    n = int(get_input().strip())
    arr = []
    for i in range(n):
        arr.append(int(get_input().strip()))
    arr.sort()

    close_val_to_zero = 0
    # find the closest number to zero
    if len(arr) % 2 != 0:
        count_negative = int(arr[0] < 0)
        close_idx_to_zero = 0
        close_val_to_zero = arr[0]
        for i in range(1, len(arr)):
            if arr[i] < 0:
                count_negative += 1

            if abs(arr[i]) < abs(close_val_to_zero):
                close_idx_to_zero = i
                close_val_to_zero = arr[i]
        if count_negative % 2 != 0 and close_val_to_zero == 0:
            if close_idx_to_zero == len(arr) - 1:
                result = arr[close_idx_to_zero]
                arr.pop(close_idx_to_zero)
            else:
                result = arr[close_idx_to_zero + 1]
                arr.pop(close_idx_to_zero + 1)
        else:
            result = arr[close_idx_to_zero]
            arr.pop(close_idx_to_zero)
    else:
        result = 0
    idx = 0
    while idx < len(arr):
        if (arr[idx] < 0 and arr[idx + 1] < 0) or (arr[idx] > 0 and arr[idx + 1] > 0):
            if arr[idx] * arr[idx + 1] > arr[idx] + arr[idx + 1]:
                result += (arr[idx] * arr[idx + 1])
            else:
                result += (arr[idx] + arr[idx + 1])
        elif (arr[idx] < 0 < arr[idx + 1]) or (arr[idx] == 0 and arr[idx + 1] > 0):
            result += (arr[idx] + arr[idx + 1])
        elif arr[idx] < 0 and arr[idx + 1] == 0:
            result += (arr[idx] * arr[idx + 1])
        else:
            result += (arr[idx] * arr[idx + 1])
        idx += 2
    print(result)


solution()

hws2006 3년 전 2

아 해결했습니다.

의외로 반례가 많이 있었습니다. 초반에 0에 가까운 숫자를 찾는 로직을 사용한게 함정이였네요.

반례 1)

3
6
2
-5

반례 2)
3
6
-2
-5

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

문제

문제

출처

ICPC

반례 부탁드리겠습니다.

hws2006 3년 전 0

hws2006 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말