백준 30505: SASA 마니또 (Python)

문제링크

https://www.acmicpc.net/problem/30505

문제 총평

- 무난한 구현 문제

문제 접근방식

- 이번 문제는 그림을 그려보면 쉽게 풀 수 있습니다.

- 1번 예제를 그림으로 그려보면 이런 형식으로 나타낼 수 있습니다.

- 이때 5번인 세종이의 번호를 제외한 나머지 1,4 번만이 5번의 마니또가 될 수 있으므로 정답은 2 입니다.

- 이점으로 미루어 보아 나의 마니또가 정해지지 않은 사람의 수 - 세종이의 마니또 결합 유무가 가능한 사람의 수인것을 알 수 있습니다.

- 하지만 예제 2과 같이 

- 2번인 세종이의 마니또는 1,3 번이 가능하지만 3번이 3번의 마니또가 될 수 없으므로 정답은 1이므로 nojam 입니다.

- 이 점에서 정답이 2일때 자신의 마니또와 자신이 가지는 마니또가 동시에 있으면 정답이 1이 되는것을 알 수 있습니다.

 

 

정답코드

import sys; I = sys.stdin.readline
n,m = map(int,I().split())
arr = [0] + [1] * (n)
arr2 = [0] + [1] * (n)
ans = 0
for _ in range(m):
    a,b = map(int,I().split())
    arr[a] = 0
    arr2[b] = 0
c = int(I())
if not arr[c]:
    print('NOJAM')
    exit()
ans = sum(arr2) - arr2[c]
if ans == 2 and sum(arr) == 2:
    for i in range(1,n+1):
        if arr[i] and arr2[i]:
            ans = 1
            break
print(ans) if ans != 1 else print('NOJAM')

1. arr, arr2로 마니또를 하는 주체와 당하는 주체를 따로 나누어 줍니다.
2. 그 결과에서 세종이의 마니또가 정해졌다면 NOJAM을 출력하고 종료합니다.
3. 위의 설명과 같이 정답은 마니또가 정해지지 않은 인원 - 세종이의 마니또 유무입니다.
4. 이떄 정답이 2 이고 자신의 마니또와 마니또를 해야할 친구조차 정해지지 않은 사람이 있다면 정답을 1로 바꿔줍니다.

문제 풀이 후 생각

- 조건을 그림으로 그려보면 풀리는 문제가 많은거 같습니다.

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요