peopleCnt = sc.nextInt();
foodCnt = sc.nextInt();
foods = new boolean[foodCnt][peopleCnt];
eats = new int[foodCnt];
friends = new String[peopleCnt];
makeFoods(sc);
private static void makeFoods(Scanner sc) {
for (int i = 0; i < peopleCnt; i++) {
friends[i] = sc.next();
}
for (int i = 0; i < foodCnt; i++) {
eats[i] = sc.nextInt();
for (int j = 0; j < eats[i]; j++) {
int pos = findFriendPos(sc.next());
foods[i][pos] = true;
}
}
}
각 음식마다 모든 친구들이 먹을수 있는 최소 음식 수를 구한다.
이때 순서는 가장 많은 친구들에게 제공하는 음식 기준입니다.
int min = 0;
for (int j = 0; j < foodCnt; j++) {
if (j == 0) {
min = changeTrue(j);
} else {
min = Math.min(min, changeTrue(j));
}
}
private static int changeTrue(int index) {
boolean[] sol = foods[index].clone();
int addIndex = -1;
int addCnt = 1;
// sol 배열이 모두 true가 될때까지 구합니다.
while (true) {
int changeCnt;
int max = 0;
for (int i = 0; i < foodCnt; i++) {
if (i == index) continue;
changeCnt = 0;
for (int j = 0; j < foods[i].length; j++) {
if (sol[j]) continue;
// 이미 true인 것을 제외하고 해당 음식이 true이면 횟수 증가
if (foods[i][j]) {
changeCnt++;
}
}
int m = Math.max(changeCnt, max);
// true가장 많이 바뀐것을 구함
if (m != max) {
addIndex = i;
max = m;
}
}
// 모두 true이면 Loop 중지
if (max == 0)break;
if (addIndex >= 0) {
// true가장 많이 바뀐 음식을 비교하여 true로 변경
sol = addTrue(sol,addIndex);
addCnt++;
}
}
// 음식 횟수 리턴
return addCnt;
}
비교하여 최소 음식수를 구한다.
System.out.println(String.valueOf(min));
전체 코드
public class Main {
//ALLERGY
private static boolean[][] foods;
private static int[] eats;
private static int peopleCnt;
private static int foodCnt;
private static String[] friends;
public static void main(String[] args) throws FileNotFoundException {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
peopleCnt = sc.nextInt();
foodCnt = sc.nextInt();
foods = new boolean[foodCnt][peopleCnt];
eats = new int[foodCnt];
friends = new String[peopleCnt];
makeFoods(sc);
int min = 0;
for (int j = 0; j < foodCnt; j++) {
if (j == 0) {
min = changeTrue(j);
} else {
min = Math.min(min, changeTrue(j));
}
}
System.out.println(String.valueOf(min));
}
}
private static void makeFoods(Scanner sc) {
for (int i = 0; i < peopleCnt; i++) {
friends[i] = sc.next();
}
for (int i = 0; i < foodCnt; i++) {
eats[i] = sc.nextInt();
for (int j = 0; j < eats[i]; j++) {
int pos = findFriendPos(sc.next());
foods[i][pos] = true;
}
}
}
private static int changeTrue(int index) {
boolean[] sol = foods[index].clone();
int addIndex = -1;
int addCnt = 1;
while (true) {
int changeCnt;
int max = 0;
for (int i = 0; i < foodCnt; i++) {
if (i == index) continue;
changeCnt = 0;
for (int j = 0; j < foods[i].length; j++) {
if (sol[j]) continue;
if (foods[i][j]) {
changeCnt++;
}
}
int m = Math.max(changeCnt, max);
if (m != max) {
addIndex = i;
max = m;
}
}
if (max == 0)break;
if (addIndex >= 0) {
sol = addTrue(sol,addIndex);
addCnt++;
}
}
return addCnt;
}
private static boolean[] addTrue(boolean[] sol, int index){
for (int i = 0; i < foods[index].length; i++) {
if(sol[i]) continue;
if(foods[index][i]) sol[i]=true;
}
return sol;
}
private static int findFriendPos(String friendName) {
int result = -1;
for (int i = 0; i < peopleCnt; i++) {
if (friends[i].equals(friendName)) {
result = i;
break;
}
}
return result;
}
}
위 코드로 제출시 에러가 발생하는데 이유를 모르겠습니다.
고수분들의 조언 부탁드립니다.
8년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
kasia
ALLERGY 문제 질문드립니다.
ALLERGY가 있는 친구들이 먹을 수 있는 음식수의 최소 갯수를 구하는 문제입니다.
이차원 배열로 먹을 수 있는 음식수를 정의한다.
peopleCnt = sc.nextInt();
foodCnt = sc.nextInt();
foods = new boolean[foodCnt][peopleCnt];
eats = new int[foodCnt];
friends = new String[peopleCnt];
makeFoods(sc);
private static void makeFoods(Scanner sc) {
for (int i = 0; i < peopleCnt; i++) {
friends[i] = sc.next();
}
for (int i = 0; i < foodCnt; i++) {
eats[i] = sc.nextInt();
for (int j = 0; j < eats[i]; j++) {
int pos = findFriendPos(sc.next());
foods[i][pos] = true;
}
}
}
각 음식마다 모든 친구들이 먹을수 있는 최소 음식 수를 구한다.
int min = 0;
for (int j = 0; j < foodCnt; j++) {
if (j == 0) {
min = changeTrue(j);
} else {
min = Math.min(min, changeTrue(j));
}
}
private static int changeTrue(int index) {
boolean[] sol = foods[index].clone();
int addIndex = -1;
int addCnt = 1;
// sol 배열이 모두 true가 될때까지 구합니다.
while (true) {
int changeCnt;
int max = 0;
for (int i = 0; i < foodCnt; i++) {
if (i == index) continue;
changeCnt = 0;
for (int j = 0; j < foods[i].length; j++) {
if (sol[j]) continue;
// 이미 true인 것을 제외하고 해당 음식이 true이면 횟수 증가
if (foods[i][j]) {
changeCnt++;
}
}
int m = Math.max(changeCnt, max);
// true가장 많이 바뀐것을 구함
if (m != max) {
}
비교하여 최소 음식수를 구한다.
System.out.println(String.valueOf(min));
전체 코드
public class Main {
//ALLERGY
}
위 코드로 제출시 에러가 발생하는데 이유를 모르겠습니다.
고수분들의 조언 부탁드립니다.
8년 전