글 읽기 - 1017_소수 쌍 해결 방법을 찾지 못해 도움을 요청드립니다.

jsy8481 4년 전 0

16%정도에서 틀렸다고 나왔습니다. (혹시 참고가 될 까 싶어 적습니닷)

코드의 흐름은

먼저 1번 숫자를 빼서 홀수 짝수를 판단하고

left에는 그 숫자와 반대되는 수를 담았습니다.

그 후 1번과 소수가 될 수 있는 값을 뽑았습니다.

이후 그래프를 그리기 위해 left right 두 리스트의 값을 비교하여 left에서 right 를 더해 소수가 된다면 이를

edge에 추가해두었고

dfs 최대 유량 알고리즘을 이용하였습니다.

그래프는 딕셔너리를 이중으로 사용하여 {시작점 : { 도착점 : weight}} 구조로 만들었습니다.

0 이 되는 엣지를 중간에 제거하는 방법으로 계산 횟수를 줄였습니다. -> 제거해도 코드가 진행을 되더라구요..

어떤 부분이 오류가 될지 몰라 이것 저것 두서 없이 쓴 점 죄송합니다.

읽어주셔서 감사합니다. 도움을 부탁드려요!!

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int,input().strip().split()))

index_1 = numbers[0]

# 첫 번째 수가 홀수 인지 찾는다.
odd_flag = 0
if index_1 % 2 == 1:
    odd_flag = 1
# 첫 번째 수를 제외하고 홀 수 짝수 그룹은 나눈다.
odds = [n for n in numbers[1:] if n % 2 == 1]
evens = [n for n in numbers[1:] if n % 2 == 0]

# left에는 1번 값과 반대되는 값을 둔다. 홀수라면 짝수 짝수라면 홀수
if odd_flag == 0:
    left = odds
    right = evens
else:
    left = evens
    right = odds
    
# 1 번째 값과 짝을 이루어서 소수가 될 수 있는 값을 리스트로 반환
source = []
for i in left:
    v = i+index_1
    root_v = int(v**(1/2))
    flag = 1
    for j in range(2,root_v+1):
        if v % j == 0:
            flag = 0
            break
    if flag == 1:
        source.append(i)
# left right 가 연결 될 수 있는 엣지를 찾는다. left+right의 합이 소수인지 체크
edge = dict([(i,[]) for i in left])

for i in left:
    for j in right:
        v = i+j
        root_v = int(v**(1/2))
        flag = 1
        for k in range(2,root_v+1):
            if v % k == 0:
                flag =0
                break
        if flag == 0:
            continue
        edge[i].append(j)
destination= 3000
start = 0

#dfs로 경로 탐색
def search(current):
    visit[current] = 1
    for d in graph[current]:
        # weight가 0인건 제거하자 -> 0인 간선은 제거함으로 따로 표현 x
        if visit[d] == 1:
            continue
        else:
            if visit[destination] == 1:
                return 1
            parent[d] = current
            search(d)
            
# 시작 지점 s 도착지점 destination
answer = []
for s in source:
    # 그래프를 구성하는 과정
    use_left = [i for i in left if i !=s]
    graph = dict([(i,{}) for i in use_left])
    graph[s] = {}
    
    for g in use_left:
        graph[s][g] =1
        for r in edge[g]:
            graph[g][r] = 1
    
    for r in right:
        graph[r] = {}
        graph[r][destination] = 1
    graph[destination] = {}
    while True:
        visit = dict([(i,0) for i in graph])
        parent= dict([i,None] for i in graph)
        search(s)
        if visit[destination] == 0:
            break
        end = destination
        while True:
            pa = parent[end]
            if pa == None:
                break
            del graph[pa][end]
            graph[end][pa] = 1
            end = pa
            
    if len(graph[destination]) == len(right):
        answer.append(s)
        
if len(answer) > 0:
    answer.sort()
    for a in answer[:-1]:
        print(a,end=' ')
    print(answer[-1])
else:
    print(-1)
    

jsy8481 4년 전 1

그래프 구성을 소스 left right 종료

로 구성하고 right의 모든 노드가 종료로 1을 보낸 경우 연결을 시켰습니다.

생각해보니 left와 right 즉 홀수 짝수의 갯수가 다른 경우가 있을 때 예를 들면 홀수가 100개 짝수가 2개라면

제가 위에 짠 코드로는 짝수 2개만 짝을 이루어도 답으로 인정되었습니다.

최대 갯수는 n //2 이고 이미 1과 연결된 하나를 뽑았음으로 n//2 -1 과 일치하는지 마지막 노드의 간선의 수랑 이를 비교하여 해결하였습니다.

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

문제

문제

출처

ICPC

1017_소수 쌍 해결 방법을 찾지 못해 도움을 요청드립니다.

jsy8481 4년 전 0

jsy8481 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말