barcelonamessi   7년 전

이분매칭 시도해서 풀어봤는데 왜 틀렸는지 잘 모르겠습니다.

코드가 좀 복잡해서 봐주실지 모르겠지만 ㅜㅜ 나름 제 코드 내용 적어볼게요


자료구조 : 홀수만 저장하는 배열 , 짝수만 저장하는 배열

전체 배열에 입력 받으면서 짝수면 짝수배열에 저장, 홀수면 홀수배열에 저장, 각각 홀수와 짝수의 개수를 저장하면서 올려줌.

입력받고 sosu 배열에 1이면 소수 0이면 소수 아니게 저장함.

입력 다 받고나서 홀수의 개수와 짝수의 개수가 다르면 -1 출력

홀수의 개수와 짝수의 개수가 같다면

(개수가 n개라면 0~n-1 인덱스 까지 배열이 저장되있음.)

1~n-1 인덱스 검사하면서 첫번째 입력받은 숫자와의 합이 소수이면

이분 매칭을 시도함. 

이분매칭할 때 홀수 배열, 짝수 배열을 이용하고 만약 과정중에 절대로 바뀌면 안되는 두 개의 수가 발견되면

진행을 건너뛰게하였음. 이 과정에서 이분매칭의 숫자가 n/2-1개이면(1개는 이미 처음에 했으므로 뺌)

소수쌍 성공으로 받아들이고 벡터에 저장함. 

이과정 끝내고 벡터가 비었다면 만족하는것이 없으므로 -1 출력 . 그 외엔 벡터를 정렬하고 오름차순으로 출력.


제 예상은 dfs과정에서 완벽히 정해진 수를 건너뛰는과정 (arr[0]이나 arr[0]과 합해서 소수가 된 수는 다른 수와 매칭되어서는 안되므로


건너뜀) 에서 착오가 있는것 같은데 정확히모르겠습니다




barcelonamessi   7년 전

자체 해결하였습니다..

별거 아닌 실수 였는데요 ㅜㅜ

bimatching 함수에서는 0번째와 i번째를 묶었다고 가정하고 그 나머지에 대해 매칭하여 매칭 개수를 가져옵니다.

dfs함수는 현재 홀수배열의 cur번째 index에서 짝수배열로 이동할 수 있는지 여부를 판단해줍니다.

가장 큰 실수가 back이라는 배열에서 나왔는데요.

back배열은 짝수 배열의 인덱스가 홀수 배열에 연결이 되어있지 않다면 -1, 연결이 되어있다면 연결된 홀수 배열의 인덱스를 저장합니다.


그런데 저는 이 back 배열을 처음에 

for(int i=0; i<N; i++)

back[i]=0; 

으로 해서 본의 아니게 연결이 되어있지 않아야할 배열이 0번째 인덱스를 가리키게 되었습니다.

back[i]=0; 이걸-1로 바꾸니까 해결됬네요. ㅜㅜ



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