문제
https://www.acmicpc.net/problem/16960
접근
- N개의 스위치마다 해당 스위치를 누르지 않았을 때 M개의 모든 램프를 켤 수 있는지 확인한다.
- 한 스위치에 M개의 램프가 연결된 경우에는 항상 N-1개의 스위치로 모든 램프를 켤 수 있기 때문에, 실제 시간 복잡도는 이론상 계산한 O(N^2 * M) 보다 훨씬 작을 것이다.
풀이
- 각 스위치에 연결된 램프를 저장하기 위해 딕셔너리 사용
- 각 스위치를 누르지 않았을 때 N-1개의 스위치로 모든 램프를 켤 수 있는지 check 배열로 확인
n, m = map(int, input().split())
connect = dict()
for i in range(1, n + 1):
k, *num = map(int, input().split())
connect[i] = num
for i in range(1, n + 1):
check = [False] * (m + 1)
for j in range(1, n + 1):
if i == j:
continue
for x in connect[j]:
check[x] = True
if sum(check) == m:
print(1)
break
else:
print(0)
'Python > Coding Test' 카테고리의 다른 글
2485 가로수 (0) | 2022.02.14 |
---|---|
19235 모노미노도미노 (0) | 2022.02.13 |
1781 컵라면 (0) | 2022.02.10 |
17175 피보나치는 지겨웡~ (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |