글 읽기 - 도와주세요~~! T.T 예외 케이스가 있은지...50%에서 틀리다고 하네요.

myth 6년 전 0

몇 가지 테스트 케이슬 입력해 봤는데...

잘됩니다.

어떤 코너 Case가 있길래 50%에서 틀리다고 하는지 모르겠네요.

고수님들의 고견 부탁 드립니다~~~ (꾸벅)

package 백준_책나누어주기;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	static int[] applicants;
	static int[] selectedApp;
	static int[][] visitedEdges;
	static int bookCnt = 0;
	static int appCnt = 0;
	static ArrayList<Integer>[] wantedBooks;
	
	public static boolean DFS(int stNum, int edNum) {
		
        // 현재 선택된 책 기준으로 해당 책은 이용하려는 사람들에 대해서 Match되는 책을 찾는다. 
		for (int i : wantedBooks[stNum]) {	
			
            // 기존에 연결되었던 Edge(이전 책과 사람과의 match)는 건너뛴다.
            if (visitedEdges[stNum][i] > 0)
				continue;
			visitedEdges[stNum][i] = 1;
			
            // 연결이 안되어 있는 이용자가 있으면 OK, 없으면 해당 책에 기존에 연결되었던 이용자 부터
            // DFS검색한다.
			if (applicants[i] == 0 || DFS(applicants[i], i) ) {				
				applicants[i] = stNum;							
				return true;				
			}
            
		}
        
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int caseCnt = sc.nextInt();
		
		for (int i=0; i<caseCnt; i++) {
			
			bookCnt = sc.nextInt();
			appCnt = sc.nextInt();
			
            int stNum = 0;
		    int edNum = 0;
		    int matchCnt = 0;
            
			wantedBooks = new ArrayList[bookCnt+2];	
			applicants = new int[appCnt+2];
			selectedApp = new int[bookCnt+2];
			visitedEdges = new int[bookCnt+2][appCnt+2];
			
			for (int j=1; j<bookCnt+1; j++)
				wantedBooks[j] = new ArrayList<Integer>();
						
			for (int j=1; j<appCnt+1; j++) {
				
				stNum = sc.nextInt(); // 가지고자 하는 책의 시작 번호
				edNum = sc.nextInt(); // 가지고자 하는 책의 끝 번호
				
				// 책 기준으로 어느 사람들에게 줄 것인가? 로 변환 입력
				// (찾지 않는 책은 검색 조차 필요없으므로~)
				if (stNum <= bookCnt && edNum <= bookCnt) {
					for (int k = stNum; k<=edNum; k++) {
						wantedBooks[k].add(j);
					}		
				}				
			}
						
			for (int j=1; j<bookCnt+1; j++) {			
				if (DFS(j, 0)) {					
					matchCnt++;					
				}
			}			
			System.out.println(matchCnt);
			
		}
		sc.close();
	}
}

djghdy 6년 전 0

혹시 푸셨나요 저도 계속 50퍼에서 틀립니다 ..

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

문제

문제

출처

ICPC

도와주세요~~! T.T 예외 케이스가 있은지...50%에서 틀리다고 하네요.

myth 6년 전 0

djghdy 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말