글 읽기 - 1017번 8%에서 틀리는데 원인 알 수 있을까요??

ikth6001 5년 전 0

1017번 소수쌍 문제 도전 중인데요 8%에서 계속 틀리는데 원인을 알 수 없습니다. 원인좀 알 수 있을까요??

답변 글을 보고 내용 추가합니다.

방법은 인터넷 검색을 통해 알게된 이분매칭 기법을 사용했습니다.

main에서는 입력값을 읽는 것이고, calculate 메소드에 실제 풀이 로직이 있습니다.

첫 번째 데이터인 data[0]을 기준으로 이분매칭에서 왼쪽에 해당하는 노드들을 결정합니다(data[0]이 짝수이면 짝수인 수들, 홀수이면 홀수인 수들).

이후엔 왼쪽에 있는 데이터와 오른쪽에 있는 데이터의 합을 통해 소수인 경우 adj라는 이분매칭에서 노드의 연결이 될 간선 정보들을 업데이트 합니다.

그 다음엔 DFS를 통한 이분매칭을 계산하고, 계산한 리턴 값 count가 실제 data길이의 반인 경우엔 첫번째 데이터인 data[0]의 다음 노드를 list에 넣어두고 마지막으로 정렬한 후 출력해줍니다.

질문을 너무 대충 올린것 같네요. 죄송합니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


public class Main 
{
	private final int MAX_ARRSIZE= 1001;
	private final int EMPTY= -1;
	
	public static void main(String[] args) 
	{
		Main m= new Main();
		
		Scanner scanner= new Scanner(System.in);
		
		int size= scanner.nextInt();
		
		int[] data= new int[size];
		
		for(int i=0; i<size; i++)
		{
			data[i]= scanner.nextInt();
		}
		m.calculate(data);
		
		scanner.close();
	}
	
	
	private void calculate(int[] data)
	{
		int leng= data.length;
		int target= data[0];
		List<Integer> lefts= new ArrayList<>();
		Map<Integer, List<Integer>> adj= new HashMap<>();
		
		for(int i=0; i<leng; i++)
		{
			int fst= data[i];
			
			/**
			 * 이분매칭에서 좌측 노드가 될 대상들
			 */
			if(target % 2 == fst % 2)
			{
				lefts.add(fst);
			}
			
			for(int j=i+1; j<leng; j++)
			{
				int snd= data[j];
				
				/**
				 * DFS를 활용한 이분매칭에 사용될 간선정보
				 */
				if(isPrime(fst + snd))
				{
					if(adj.get(fst) == null) 
					{
						adj.put(fst, new ArrayList<>());
					}
					
					if(adj.get(snd) == null) 
					{
						adj.put(snd, new ArrayList<>());
					}
					
					adj.get(fst).add(snd);
					adj.get(snd).add(fst);
				}
			}
		}
		
		if(lefts.size() == 0 || lefts.size() != leng / 2 || adj.get(target) == null || adj.get(target).size() == 0)
		{
			System.out.println("-1");
			return;
		}
		
		List<Integer> answer= new ArrayList<>();
		
		Set<Integer> used= new HashSet<>();
		for(int dest : adj.get(target))
		{
			int[] connection= new int[MAX_ARRSIZE];
			for(int i=0; i<MAX_ARRSIZE; i++)
			{
				connection[i]= EMPTY;
			}
			connection[dest]= target;
			
			used.clear();
			used.add(target);
			
			int cnt= bipartite(connection, used, lefts, adj) + 1;
			
			if(cnt >= (leng / 2) && !answer.contains(dest))
			{
				answer.add(dest);
			}
		}
		
		Collections.sort(answer);
		
		for(Integer num : answer)
		{
			System.out.print(num + " ");
		}
	}
	
	private int bipartite(int[] connection, Set<Integer> used, List<Integer> lefts, Map<Integer, List<Integer>> adj)
	{
		int cnt= 0;
		
		Set<Integer> clone= new HashSet<>();
		for(int left : lefts)
		{
			clone.clear();
			clone.addAll(used);
			
			if(dfs(connection, clone, left, adj))
			{
				cnt++;
			}
		}
		
		return cnt;
	}
	
	private boolean dfs(int[] connection, Set<Integer> used, int left, Map<Integer, List<Integer>> adj)
	{
		if(used.contains(left))
		{
			return false;
		}
		
		used.add(left);
		
		for(int right : adj.get(left))
		{
			if( connection[right] == EMPTY || dfs(connection, used, connection[right], adj) )
			{
				connection[right]= left;
				return true;
			}
		}
		return false;
	}
	
	private boolean isPrime(int num) 
	{
		int max= num/2;
		
		for(int i=2; i<=max; i++) 
		{
			if(num % i == 0) 
			{
				return false;
			}
		}
		return 1 < num ? true : false;
	}

}

jh05013 5년 전 0

이렇게 설명 하나 없이 긴 코드는 아무도 읽을 엄두를 안 낼 것입니다. 적어도 어떻게 접근하셨는지 정도는 설명해 주세요.

그 이전에, 질문을 올릴 때 "아래 공지사항을 먼저 읽고 글을 작성해 주세요." 라는 말이 나오는데 읽으셨나요? 정말로 읽으셨으면 굵은 글씨로 작성된 이 문장도 읽으셨을 것입니다.

https://www.acmicpc.net/board/...

"질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요."

ikth6001 5년 전 0

마지막에

if(answer.isEmpty())

{

System.out.println(EMPTY);

return;

}

를 통해 첫번째 값과 연결되는 두번째 값이 없을경우에 대한 처리를 안해줘서 문제가 됬었네요.. 인터넷 검색 후 제 로직과 비교하면서 빠진 부분을 찾아서 해결했습니다...

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

문제

문제

출처

ICPC

1017번 8%에서 틀리는데 원인 알 수 있을까요??

ikth6001 5년 전 0

jh05013 5년 전 0

ikth6001 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말