[백준/파이썬][Silver III] Contaminated Milk - 11972

[Silver III] Contaminated Milk - 11972

문제 링크

성능 요약

메모리: 114012 KB, 시간: 120 ms

분류

브루트포스 알고리즘, 구현

제출 일자

2025년 2월 7일 00:50:44

문제 설명

Farmer John, known far and wide for the quality of the milk produced on his farm, is hosting a milk-tasting party for $N$ of his best friends $1 \leq N \leq 100$. Unfortunately, of the $M$ types of milk featured at the party $1 \leq M \leq 50$, exactly one of them has gone bad, but Farmer John does not know which one! Anyone who drinks the bad milk will later become sick, either during the remainder of the party or afterward.

You are given a transcript of the party -- who drinks what when, and also who gets sick when. Based on this information, you can deduce which of the milks could possibly be the bad one. Using this knowledge, help Farmer John determine the minimum number of doses of medicine he will need to obtain in order to guarantee that he can cure all of the individuals who become sick, either during or after the party.

입력

The first line of the input contains integers $N$, $M$, $D$, and $S$.

The next $D$ lines $1 \leq D \leq 1000$ each contain three integers $p$, $m$, $t$, indicating that person $p$ drank milk $m$ at time $t$. The value of $p$ is in the range $1 \ldots N$, $m$ is in the range $1 \ldots M$, and $t$ is in the range $1 \ldots 100$. A person may drink the same milk several times, and may also drink several types of milk at the same point in time.

The next $S$ lines $1 \leq S \leq N$ each contain two integers $p$,$t$, indicating that person $p$ gets sick at time $t$. The value of $p$ is in the range $1 \ldots N$, and $t$ is in the range $1 \ldots 100$. Each person gets sick at most once, and they only get sick because they drank the bad milk at some strictly earlier point in time.

출력

A single integer, specifying the minimum number of doses of medicine Farmer John needs to obtain so that he can guarantee that he will have sufficiently many doses to treat all the people who become sick, both during and after the party.

풀이

from collections import defaultdict

def find_min_medicine(N, M, D, S, party, sick) :
    drinks = defaultdict(set)   # 각 사람이 마신 우유 종류 저장
    sick_times = {} # 병에 걸린 사람과 그 시간 저장

    for p, m, t in party :
        drinks[p].add((m, t))

    for p, t in sick :
        sick_times[p] = t

    # 상한 우유 후보 찾기
    possible_bad_milk = set(range(1, M + 1))
    for p, sick_time in sick_times.items() :
        possible_milks = set()
        for m, t in drinks[p] :
            if t < sick_time :
                possible_milks.add(m)
        possible_bad_milk &= possible_milks # 모든 아픈 사람이 공통으로 마신 우유만 남김(교집합)

    # 최악의 경우 감염될 수 있는 최대 사람 수 찾기
    max_sick_count = 0
    for bad_milk in possible_bad_milk :
        infected = set()
        for p in range(1, N+1) :
            if any(milk == bad_milk for milk, time in drinks[p]) :
                infected.add(p)
        max_sick_count = max(max_sick_count, len(infected))

    return max_sick_count

def main() :
    N, M, D, S = map(int, input().split())

    party = [list(map(int, input().split())) for _ in range(D)]
    sick = [list(map(int, input().split())) for _ in range(S)]

    print(find_min_medicine(N, M, D, S, party, sick))

main()

📌 코드 설명

def main() :
    N, M, D, S = map(int, input().split())

    party = [list(map(int, input().split())) for _ in range(D)]
    sick = [list(map(int, input().split())) for _ in range(S)]

    print(find_min_medicine(N, M, D, S, party, sick))

1️⃣ 입력값을 저장하는 과정

• N: 사람의 수
• M: 우유 종류의 수
• D: 사람들이 우유를 마신 기록 개수
• S: 사람들이 아픈 기록 개수

def find_min_medicine(N, M, D, S, party, sick) :
    drinks = defaultdict(set)   # 각 사람이 마신 우유 종류 저장
    sick_times = {} # 병에 걸린 사람과 그 시간 저장

    for p, m, t in party :
        drinks[p].add((m, t))

    for p, t in sick :
        sick_times[p] = t

(1) drinks 딕셔너리 생성

• drinks[p] = set() : 각 사람 p가 마신 (우유 종류, 시간) 정보를 저장하는 집합
• drinks[p].add( (m, t) ) : p번 사람이 t 시간에 m번 우유를 마심

(2) sick 딕셔너리 생성

• sick_times[p] = t : p번 사람이 t 시간에 아픔

---

# 상한 우유 후보 찾기
possible_bad_milk = set(range(1, M + 1))
for p, sick_time in sick_times.items() :
    possible_milks = set()
    for m, t in drinks[p] :
        if t < sick_time :
            possible_milks.add(m)
    possible_bad_milk &= possible_milks # 모든 아픈 사람이 공통으로 마신 우유만 남김(교집합)

2️⃣ 상한 우유 후보 찾기

(1) possible_bad_milk 초기화

• set(range(1, M + 1)) : 처음에는 모든 1~M번 우유가 상했다고 가정

(2) 모든 아픈 사람에 대해 확인

• {milk for milk, time in drinks[p] if time < t}
  → p번 사람이 t 시간 전에 마신 우유만 선택
• possible_bad_milk &= possible_milks
  → 교집합 연산 (&=) 사용
  → 모든 아픈 사람이 공통으로 마신 우유만 남김

📌 결과적으로, 모든 아픈 사람이 공통으로 마신 우유만 남음
📌 즉, possible_bad_milk에는 상했을 가능성이 있는 우유만 포함됨

---

# 최악의 경우 감염될 수 있는 최대 사람 수 찾기
max_sick_count = 0
for bad_milk in possible_bad_milk :
    infected = set()
    for p in range(1, N+1) :
        if any(milk == bad_milk for milk, time in drinks[p]) :
            infected.add(p)
    max_sick_count = max(max_sick_count, len(infected))

return max_sick_count

3️⃣ 최대 감염자 수 계산

(1) 모든 의심스러운 우유에 대해 감염자 수를 계산

• bad_milk in possible_bad_milk : 상했을 가능성이 있는 우유 하나씩 확인
• infected = set() : 감염된 사람 저장

(2) any()를 사용하여 특정 우유를 마신 사람 찾기

if any(milk == bad_milk for milk, time in drinks[p]) :
    infected.add(p)

• p번 사람이 bad_milk를 마셨다면 infected에 추가

(3) max_infected 갱신

max_sick_count = max(max_sick_count, len(infected))

• 여러 상한 우유 후보 중에서 가장 많은 감염자를 발생시키는 경우를 선택

📌 결과적으로, 최악의 경우를 가정하여 필요한 약의 최소 개수를 결정함

---

🚀 예제 실행 과정

🔹 입력 예제

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

🔹 데이터 정리

사람마신 우유 (시간)

1	(1,1), (4,1), (3,4), (2,2)
2	(1,5), (2,7)
3	(1,3)

사람아픈 시간

1	3
2	8

🔹 1. 상한 우유 후보 찾기

• 1번은 1, 2, 4번 우유 마심
• 2번은 1, 2번 우유 마심
  ✅ 가능한 상한 우유: {1, 2}

🔹 2. 최대 감염자 수 계산

① 1번 우유가 상했다면

• 1번 우유를 마신 사람: {1, 2, 3}
• 감염자 수: 3

② 2번 우유가 상했다면

• 2번 우유를 마신 사람: {1, 2}
• 감염자 수: 2

✅ 최대 감염자 수: 3 (최소 3개의 약 필요)

🔹 최종 출력

3

---

📌 핵심 정리

1️⃣ 모든 아픈 사람이 마신 우유의 교집합을 구해 상한 우유 후보를 찾음
2️⃣ 각 의심스러운 우유를 기준으로 최대 감염자 수를 계산
3️⃣ 가장 큰 감염자 수를 출력 (필요한 최소한의 약 개수)

🚀 집합 연산 (&=, set(), any())을 활용하여 빠르고 효율적인 연산을 수행
📌 O(NM + D + S) 정도의 시간 복잡도로 문제를 해결 가능!