글 읽기 - 1017번 반례가 궁금합니다.

qowhdgn 2년 전 0

안녕하세요

1017번 문제 몇번째 제출하는데 반례를 찾기 쉽지 않네요 ㅠㅠ

게시판에 나온 반례들을 체크해봐도 결과는 잘 나오는 것 같은데

혹시 반례가 더 있을까요..?

시도한 케이스

6
1 4 7 10 11 12
=> 4 10

8
1 4 7 10 11 12 14 16
=> -1

8
1 2 3 4 5 6 7 8
=> 2 4 6

2
597 22
=> 22

2
1 2
=> 2

2
2 1
=> 1

2
1 3
=> -1

#소수 쌍
import sys

N = int(sys.stdin.readline())
primeArr = [1]*2000 #1000 이하의 자연수 쌍의 최대합=1000+999, 중복X
odds = list()
evens = list()

#소수 리스트
for i in range(2,len(primeArr)):
    for j in range(i+i,len(primeArr),i):
        primeArr[j] = 0

#소수는 2 제외하면 모두 홀수
#중복 없는 A, B에 대해 A+B는 3 이상의 소수

line = list(map(int,sys.stdin.readline().split()))

for i in range(0,len(line)):
    if line[i]%2 == 0:
        evens.append(line[i])
    else:
        odds.append(line[i])

def bipartileMatch(oddList,evenList): #이분매칭
    if len(oddList)==len(evenList) and len(oddList)==1: #마지막 숫자 쌍 체크
        return primeArr[oddList[0] + evenList[0]] #소수면 1(true)

    answer = False
    for i in range(len(oddList)):
        odd = oddList.pop(i)
        for j in range(len(evenList)):
            even = evenList.pop(j)

            if primeArr[odd+even]:
                answer = bipartileMatch(oddList, evenList)
                evenList.insert(j, even)

                if answer:
                    oddList.insert(i, odd)
                    return True

            else:
                evenList.insert(j,even)
                oddList.insert(i, odd)
                return False

        oddList.insert(i,odd)

answerList = list()

if N == 2 and len(evens) == 1 and len(odds) == 1:
    if primeArr[evens[0]+odds[0]]:
        if line[0] % 2 == 0:
            answerList.append(odds[0])
        else:
            answerList.append(evens[0])


elif len(evens)==len(odds):
    if line[0]%2==0: #첫 수가 짝수
        even = evens.pop(0)

        for i in range(len(odds)):
            odd = odds.pop(i)
            if primeArr[even+odd]==0: #소수 아닐 때
                odds.insert(i, odd)
            else:
                if bipartileMatch(odds,evens): #현재 뽑은 수 제외한 리스트를 넘기기
                    answerList.append(odd)
                odds.insert(i,odd)


    else: #첫 수가 홀수
        odd = odds.pop(0)

        for i in range(len(evens)):
            even = evens.pop(i)
            if primeArr[odd+even]==0: #소수 아닐 때
                evens.insert(i, even)
            else:
                if bipartileMatch(odds,evens):
                    answerList.append(even)
                evens.insert(i,even)

if len(answerList)==0:
    print(-1)
else:
    answerList.sort()
    print(*answerList)

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

문제

문제

출처

ICPC

1017번 반례가 궁금합니다.

qowhdgn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말