백준 11972 contaminated milk - usaco 브론즈 완전탐색 python 풀이

문제 링크

www.acmicpc.net/problem/11972

11972번: Contaminated Milk

풀이 아이디어

문제의 간단한 해석을 하자면 오염된 우유는 단 1종류이고,

이 우유를 마신 사람은 파티 도중에 식중독이 올 수도 있고 안올 수도 있는데 

확실한 건 우유를 마신 시각 반드시 '이후'에 발병이 된다는 것이다.

이때 아플 수 있는 최대한의 사람의 수를 구하는 것이 문제이다.

 

나는 countlist라는 리스트를 만든 후 전부 0으로 초기화를 시켜주었다.

그리고 어떤 사람이 발병이 된 이전에 그 사람이 마신 우유를 전부 count +=1 시켜 주었다.

그렇게 하면 아픈 사람의 수와 count 값이 일치하는 우유들이 오염된 우유의 '후보' 인 것이다.

나머지는 이 우유를 마셨는지를 체크해 가며 마신 사람의 수가 제일 큰 값을 출력하면 문제는 끝나게 된다.

 

코드 (python)

n,m,d,s = map(int,input().split())
person = [[] for i in range(n)]
countlist = [0 for _ in range(m+1)]

for i in range(d):
    p,m,t = map(int,input().split())
    person[p-1].append((m,t))
for i in range(s):
    p,t = map(int,input().split())
    for history in person[p-1]:
        if history[1]<t:
            countlist[history[0]]+=1
ans=0
for i in range(len(countlist)):
    if countlist[i]<s:
        continue
    tmp = 0
    for per in person:
        for history in per:
            if history[0]==i:
                tmp+=1
                break
    ans = max(ans,tmp)
print(ans)