글 읽기 - 1퍼에 틀렸습니다가 뜨는데..이유를 모르겠습니다ㅠㅠ

izyy 4년 전 0

문제 테케도 맞고 게시판에 올려주신 테케도 돌려봤는데 5,2 제대로 나와요..고수님들 답변 부탁드립니다ㅠㅠ

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

public class Main {
	static int n;
	static int[] arr2;
	static int[][] arr;
	static int[] ch;
	static ArrayList<Integer> li;
	static ArrayList<Integer> li2;
	static int mi = 98765432;

	static void dfs(int idx) {
		if (idx == (n + 1)) {// 배열끝까지 갔으면 종료
			li = new ArrayList<>();
			li2 = new ArrayList<>();
			boolean num1 = false;// 1선거구 인접 여부 체크
			boolean num2 = false;// 2선거구 인접 여부 체크
			int nu1 = 0;// 1선거구 인구수 합
			int nu2 = 0;// 2선거구 인구수 합
			for (int i = 1; i <= n; i++) {
				if (ch[i] == 1)
					li.add(i);// 1팀을 li리스트에 저장합니다.
				else
					li2.add(i);// 2팀을 li2리스트에 저장합니다.
			}
			if (li.size() != 0 && li2.size() != 0) {// 두팀으로 나뉘었을 때 계산을 합니다.
				if (li.size() == 1)// 1선거구에 마을하나만 있을경우 이 마을이 1선거구의 전체 수가 됩니다
					nu1 = arr2[li.get(0)];
				else if (li.size() > 1) {// 아닐경우 인접여부를 체크합니다
					for (int i = 0; i < li.size(); i++) {
						num1 = false;
						for (int j = 0; j < li.size(); j++) {
							if (i != j && arr[li.get(i)][li.get(j)] == 1) {
								num1 = true;
								break;
							}
						}
						if (num1 == false)
							return;
					}

					for (int i = 0; i < li.size(); i++)
						nu1 += arr2[li.get(i)];
				}
				if (li2.size() == 1)// 2선거구에 마을하나만 있을경우 이 마을이 2선거구의 전체 수가 됩니다
					nu2 = arr2[li2.get(0)];
				else if (li2.size() > 1) {// 아닐경우 인접여부를 체크합니다
					for (int i = 0; i < li2.size(); i++) {
						num2 = false;
						for (int j = 0; j < li2.size(); j++) {
							if (i != j && arr[li2.get(i)][li2.get(j)] == 1) {
								num2 = true;
								break;
							}
						}
						if (num2 == false)
							return;
					}
					for (int i = 0; i < li2.size(); i++)
						nu2 += arr2[li2.get(i)];
				}
				if (mi > Math.abs(nu1 - nu2))
					mi = Math.abs(nu1 - nu2);
			}
			return;
		}
		ch[idx] = 1;
		dfs(idx + 1);
		ch[idx] = 0;
		dfs(idx + 1);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		arr = new int[n + 1][n + 1];
		arr2 = new int[n + 1];
		ch = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr2[i] = sc.nextInt();
		}
		for (int i = 1; i <= n; i++) {
			int n2 = sc.nextInt();
			for (int j = 0; j < n2; j++) {
				int n3 = sc.nextInt();
				arr[i][n3] = 1;//인접한곳 체크
			}
		}
		dfs(1);
		if (mi == 98765432)
			System.out.println(-1);
		else
			System.out.println(mi);
	}
}

puzzledpublic 4년 전 0

반례 드립니다

INPUT:

2 2 2 2 2 2

1 3

1 4

1 1

1 2

1 6

1 5

OUTPUT:

-1

izyy 4년 전 0

반례 감사합니다!생각을 잘못하고 있었네요 다시 풀어보겠습니다

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

문제

문제

출처

ICPC

1퍼에 틀렸습니다가 뜨는데..이유를 모르겠습니다ㅠㅠ

izyy 4년 전 0

puzzledpublic 4년 전 0

izyy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말