https://www.acmicpc.net/problem/12792
| 시간 제한 | 메모리 제한 |
| 1초 | 256MB |
문제
곧 다가올 학교 축제를 위해, 쿠사과는 참가비를 내고 여러 사람이 동시에 즐길 수 있는 게임을 만들었다. 이 게임의 알파이자 오메가는 추첨기이다. 이 추첨기는 1번부터 N번까지 둥글게 구멍이 위 아래로 하나씩 나 있고, 추첨기 윗편 구멍에 구슬을 넣으면 안에서 정해진 통로에 따라 복잡하게 움직이다가 아래 구멍 중 하나로 떨어지게 된다.
게임은 간단하다. N명이 동시에 모여 추첨기에서 1부터 N이 적힌 자리에 각각 한 명씩 선 뒤, 쿠사과가 1번 사람부터 N번 사람까지 차례로 돌아가면서 구슬을 하나씩 넣고, 어느 위치에 떨어지는지 본다. 만약 어떤 사람이 자신의 위치에서 넣은 구슬이 그대로 자신이 선 위치의 아래 구멍으로 나오게 되면 아무 일도 일어나지 않지만, 다른 자리에 떨어지면 그 사람은 경품을 얻게 된다. 단 모든 사람이 경품을 받는 경우, 즉 모든 사람이 자신이 선 위치와 다른 곳으로 구슬이 떨어지면 이 판은 잭팟이 되어 모두가 경품을 받지 못한다.
추첨기의 내부 동작에 대해 전혀 알 수 없는 사람들이 생각하기에는 그냥 웬만하면 경품을 얻는 꿀같은 게임이라고 생각하겠지만, 쿠사과의 생각은 조금 달랐다. 언듯 보기에는 구슬이 랜덤하게 떨어져 내려오는 것 같았지만 실제로는 사전에 정해진 결과대로 내려오기 때문이었다.
또한 추첨기를 처음 한 개 만드는 건 매우 어려웠지만 복제하는 것은 매우 간단했기 때문에, 추첨기에 똑같은 추첨기를 다시 연결하는 식으로 하면 겉에서 보기에는 하나의 추첨기이고 또 더 화려하게 움직이지만 내부적으로는 조작된 추첨기를 얻을 수 있다.
예를 들어 1 → 2, 2 → 1, 3 → 4, 4 → 3으로 구성된 추첨기가 있다면, 이건 이미 쿠사과가 무조건 이득을 보는 좋은 기계이다. 이 기계를 두 개 연결하게 되면 1 → 1, 2 → 2, 3 → 3, 4 → 4가 되어 아무런 일도 일어나지 않지만, 다시 한 개 더 연결하게 되면 처음처럼 쿠사과가 무조건 이득을 보는 좋은 기계가 된다.
이렇게 게임을 진행하면, 1번 사람부터 점점 다른 위치로 나와서 모두가 신나하다가, 점점 모두가 다른 위치로 나오는 것에 경악하게 될 것이다. 그리고 N번 사람의 구슬이 마지막 추첨기 밖으로 나오는 순간, 쿠사과는 "아이쿠 그런데 그것이 실제로 일어났습니다" 라고 말하며 즐거워할 생각에 가득차 있다.
쿠사과는 가급적이면 2개 이상의 추첨기를 서로 연결해 게임의 박진감을 불러일으키고자 한다. 추첨기가 주어질 때, 쿠사과가 이득을 보는 결과를 얻으려면 몇 개의 추첨기를 연결해야 할까?
입력
첫 줄에는 정수 N (1 ≤ N ≤ 1000000) 이 주어진다. 다음 줄에는 N개의 정수 Ji가 공백으로 구분되어 주어지며, 각 정수는 1에서 N 사이이며 끝을 포함한다. 이는 i번 자리에 선 사람이 얻게 되는 결과 정수를 뜻한다.
출력
추첨기를 몇 개 연속으로 연결하면 쿠사과가 이득을 보는 결과를 얻을 수 있는지 출력한다. 이 값은 2 이상 2 × 109 이하여야 하지만, 조작된 결과를 얻을 수만 있다면 어떤 값이든 상관없다. 만약 주어진 범위 안에서 조작할 방법이 없다면 -1을 출력하라.
풀이
문제가 굉장히 깁니다. 요약하면 1~N까지의 숫자를 1~N까지의 숫자로 섞어서 반환하는 함수 f(x)를 만든다고 생각할 수 있습니다. 그러니까 f(x)는 일대일대응 함수입니다. 여기서 f(x)를 2회 이상 k번 연속적으로 합성한 함수를 g(x)라고 합시다. y = g(x)가 모든 J에 대해 x ≠ y가 되는 k를 뭐가 되었든 2 이상, 2,000,000,000 이하의 범위에서 찾아 출력, 없다면 -1을 출력하라는 문제입니다.
문제를 보자마자 어떻게 풀어야 할지 바로 감을 잡을 수 있었는데 예전에 본 영상 때문이었습니다.
이렇게 1~N의 숫자를 1~N의 숫자에 무작위적으로 일대일대응 시켰을 때, 어떤 a에 대하여 f(a) = b, f(b) = c, f(c) = d... f(k) = a가 되는 사이클이 존재합니다. 어쩌면 f(a) = a가 나올 수도 있고, N개의 수 전부가 하나의 사이클을 이룰 수도 있습니다. 아무튼, 이 사이클을 놓고 봤을 때 길이 l인 사이클을 이루는 수 t에 대하여 f(x)를 l번 중첩시킨 합성함수의 결과는 자기 자신이며 l의 배수가 아닌 어떤 횟수로든 중첩시킨 결과는 자기 자신이 아니게 됩니다.
그렇다면 이 문제에서 원하는 결과는 존재하는 모든 사이클의 길이에 대해 배수 관계가 아닌 수이기만 하면 됩니다. 딱 이럴 때 쓰기 좋은 수가 바로 소수 입니다. 문제에서 주어진 N의 범위는 1,000,000까지입니다. 우리가 찾아야 할 사이클은 2,000,000,000 이하이기만 하면 됩니다. 그렇다면 1,000,000 보다 크고 2,000,000,000 보다 작거나 같은 어떤 소수이든 아무거나 출력해주면 되겠습니다. 적당한 소수가 1,000,000보다 큰 소수 중 가장 작은 1,000,003입니다.
그런데 1,000,003을 그대로 출력하면 틀렸습니다 가 뜹니다. -1을 출력해야 하는 경우가 있기 때문입니다. k가 존재하지 않는 경우는 어떤 사이클의 길이가 1인 경우입니다. 그 외의 모든 수에 대해 1,000,003은 배수가 아닙니다. 따라서 두 번째 줄에 주어지는 입력의 배열을 a를 순차적으로 쭉 읽어보았을 때, i번째 값 a[i]가 i + 1이라면(1부터 시작하기 때문) f(a) = a 인 사이클 1짜리 값이 존재하므로 -1을 출력합니다. O(N)만에 해결할 수 있는 문제가 되어버렸네요.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
j = list(map(int, input().split()))
for i in range(n):
if j[i] == i + 1:
print(-1)
return
print(1000003)
solution()
