[코드트리] 상해버린 치즈

이 문제는 주어진 조건에 따라 완전탐색을 하며 그 최댓값을 찾는 문제이다. 이런 류 문제는 쉽지만 조건이 까다로워서 애먹었다. 이에 기록한다.

 

---

N명의 사람이 M개의 치즈를 먹었는데 정확히 하나의 치즈가 상했다는것을 뒤늦게 알았습니다. 특정 사람이 어떤 치즈를 언제 먹었는지에 대한 기록이 총 D번 주어지고, 특정 사람이 언제 확실히 아팠는지에 대한 기록이 S번 주어지게 됩니다. 완벽하게 기록된 것이 아니기 때문에, 아프다고 기록되어 있는 사람 외의 다른 사람도 아플 수 있습니다. 상한 치즈를 먹은 사람에게 약을 복용시켜야 할 때, 약이 최대 몇 개나 필요할지를 구하는 프로그램을 작성해보세요. 단, 상한 치즈를 먹게 되면 1초가 지나야 아프기 시작하며, 상한 치즈를 먹지 않는 한 배가 아플 일은 없다고 가정해도 좋습니다.

 

입력 형식

첫 번째 줄에 사람의 수 N, 치즈의 수 M, 치즈를 먹은 기록의 수 D, 그리고 아픈 기록의 수 S가 각각 공백을 사이에 두고 주어집니다.

• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 50
• 1 ≤ D ≤ 1,000
• 1 ≤ S ≤ N

두 번째 줄부터 D개의 줄에 걸쳐 한 줄에 하나씩 몇 번째 사람(p)이 몇 번째 치즈(m)를 언제 먹었는지(t초)에 대한 정보 (p, m, t)가 공백을 사이에 두고 주어집니다.

• 1 ≤ p ≤ N
• 1 ≤ m ≤ M
• 1 ≤ t ≤ 100

그 다음에는 S개의 줄에 걸쳐 한 줄에 하나씩 몇 번째 사람(p)이 언제 확실히 아팠는지(t초)에 대한 기록 (p, t)가 공백을 사이에 두고 주어집니다. 동일한 사람이 아프다는 정보가 여러 번 주어지지 않는다고 가정해도 좋습니다. 또한, 모순된 입력 역시 주어지지 않는다고 가정해도 좋습니다.

• 1 ≤ p ≤ N
• 1 ≤ t ≤ 100

출력 형식

첫 번째 줄에 약이 최대 몇 개나 필요한지를 출력합니다.

 

입출력 예제

예제1

입력:

3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3 
2 1 5
2 2 7
1 3
2 8

출력:

3

 

예제 설명

총 3명의 사람이 4가지의 치즈를 먹었습니다. 1번 사람이 3초에 아프게 되었고, 2번 사람이 8초에 아프게 되었습니다.

1번 치즈는 1번 사람과 2번 사람이 모두 아파지기전에 먹었으니 상한 치즈일 수 있습니다. 그렇다면 3번 사람도 먹었으니 총 3명의 사람이 아프게 될 수있습니다.

2번 치즈는 1번 사람과 2번 사람이 모두 아파지기전에 먹었으니 상한 치즈일 수 있습니다. 총 2명의 사람이 아프게 될 수있습니다.

3번 치즈는 1번 사람이 아프기전에 먹지 않았기 때문에 상한 치즈일 수 없습니다.

4번 치즈는 2번 사람이 먹지 않았기 때문에 상한 치즈일 수 없습니다.

따라서 최대 3명의 사람이 아플 수 있으므로 약은 총 3개가 필요합니다.

 

내 코드

import java.util.*;

class Eat implements Comparable<Eat> {
    int p; //몇번째 사람
    int m; //몇번째 치즈
    int t; //언제 먹었는지

    Eat(int p, int m, int t) {
        this.p = p;
        this.m = m;
        this.t = t;
    }

    @Override
    public int compareTo(Eat eat) {
        return this.t - eat.t;
    }
}

class Sick implements Comparable<Sick> {
    int p; //몇번째 사람
    int t; //언제 확실히 아팠는지

    Sick(int p, int t) {
        this.p = p;
        this.t = t;
    }

    @Override
    public int compareTo(Sick sick) {
        return this.t - sick.t;
    }
}

public class Main {

    static Eat[] eatArr;
    static Sick[] sickArr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); //사람 수
        int m = sc.nextInt(); //치즈 수
        int d = sc.nextInt(); //누가 어떤 치즈를 먹었는지에 대한 기록
        int s = sc.nextInt(); //누가 언제 확실히 아팠는지에 대한 기록

        eatArr = new Eat[d];
        for (int i = 0; i < d; i++) {
            eatArr[i] = new Eat(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        sickArr = new Sick[s];
        for (int i = 0; i < s; i++) {
            sickArr[i] = new Sick(sc.nextInt(), sc.nextInt());
        }

        /**
         * 1. 아픈사람 전부 i번치즈를 먹었나?
         * 2. 그렇다면 전부 아프기전에 먹었나?
         * 3. 위 조건을 전부 만족한다면 해당 치즈를 먹은 전부를 의심한다.
         */

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
            //해당 치즈를 아픈사람 전부가 먹었는지 check
            boolean isAllEat = true;
            for (int j = 0; j < sickArr.length; j++) {
                if (!isEat(sickArr[j].p, i)) {
                    isAllEat = false;
                    break;
                }
            }

            //해당 치즈를 아픈사람 전부가 먹고, 먹은 시간이 아픈시간보다 이른지.
            if (isAllEat) {
                boolean eatBeforeSick = true;
                for (int j = 0; j < sickArr.length; j++) {
                    if (!eatBeforeSick(sickArr[j], i)) {
                        eatBeforeSick = false;
                        break;
                    }
                }
                
                //전부 만족한다면 해당 치즈를 먹은 전부가 의심 대상자이다. 모든치즈의 대상자들의 최댓값을 return한다.
                if (eatBeforeSick) {
                    max = Math.max(max,getEatPeopleCount(n, i));
                }
            }
        }
        System.out.print(max);
    }

    static int getEatPeopleCount(int n, int m) {
        int[] temp = new int[n+1];

        for (int i = 0; i < eatArr.length; i++) {
            if (eatArr[i].m == m) {
                temp[eatArr[i].p] = 1;
            }
        }
        int count = 0;
        for (int num : temp) {
            if (num == 1) {
                count++;
            }
        }
        return count;
    }

    static boolean isEat(int p, int m) {
        for (int i = 0; i < eatArr.length; i++) {
            if (eatArr[i].p == p && eatArr[i].m == m) {
                return true;
            }
        }
        return false;
    }

    static int getEatTime(int p, int m) {
        for (int i = 0; i < eatArr.length; i++) {
            if (eatArr[i].p == p && eatArr[i].m == m) {
                return eatArr[i].t;
            }
        }
        return Integer.MAX_VALUE;
    }

    static boolean eatBeforeSick(Sick sick, int m) {
        if (getEatTime(sick.p, m) < sick.t) {
            return true;
        }

        return false;
    }
}

 

사실 그렇게 어렵지는 않았던거같은데 내가 조건을 이해못해서 오래걸렸다 지우야 사랑해^^