[백준] 3258 : 컴포트

www.acmicpc.net/problem/3258

3258번: 컴포트

---

• 1시간 넘게 머릿속으로만 정리하다가 너무 복잡해져서, 노트에 그리면서 풀었더니 바로 해결했다.
• 두뇌 컴파일러만 사용하여 논리적으로 풀어내는것도 좋지만 가끔은 시각화하는것도 좋은 방법인 것 같다...
• K 만큼 점프하면서 이동을 할 경우, 도착하는 지점에 있어서 특정 패턴이 발견된다.
• 해당 패턴들이 N 번마다 반복되기 때문에, N 번의 지점들에 대해서만 저장을 해놓으면 된다.
• 저장된 패턴에서, 장애물이 먼저 나오는지 도착점이 먼저 나오는지에 따라서 K 가 가능한지 알아낼 수 있다.
• 다른 분들 풀이를 보니 무한반복을 통해 답이 나올때까지 구하셨는데, 사실 왠지 이렇게 하면 시간초과 날까봐 하지 못했던 방법이다. 문제를 너무 어렵게 생각하지 않아도 될 것 같다.

---

import sys

N, Z, M = map(int, input().split())
obs = set(map(int, input().split()))

if Z == N:                                      # 모듈러 연산 기준으로 구하기 떄문에
    Z = 0                                       # Z 값이 N 값과 같다면 0 과 비교해준다.

for K in range(1, N):                           # K 를 1부터 N까지 돌려본다
    arr = [(1 + K * x) % N for x in range(N)]   # K 만큼 점프하면서 나오는 지점들을 순서대로 쌓음
    
    for val in arr:
        if val in obs:                          # 만약 장애물이 목표치보다 먼저 나온다면
            break                               # 바로 불가능 처리
        if val == Z:                            # 목표치가 장애물에 걸리지 않고 나올 경우
            print(K)                            # 프로그램 종료
            sys.exit()