BOJ 32896(Hash Collision) 풀이

 

이미지를 누르면 문제로 이동합니다

 

 

문제를 요약하면 정의역 X={1,2,3 .... n} 에 대한 함수가 있고, c와 r 이 주어지면 f^c(r) 을 구하는 문제이다.

f^c(r) 은 f 를 c번 합성하고 r 을넣은 함수다.

 

 

이와 같이 문제에 잘 나타나 있다.

이때 1500번의 쿼리 안에 f^c(r) = c 를 만족하는 c와 r을 출력하면 된다.

 

이를 어떻게 풀 수 있을까?

 

여러 풀이가 존재하지만 이 문제는 놀랍게도 O(1) 에 해결할 수 있다.

 

  함수 f를 생각하면 어떤 함수가 주어지더라도 c=n 이라면 최소 한번 이상 사이클이 돌게 될것이다.

이는 자명하니 넘어가겠다. 이에 대해서는 몇가지 예제를 만들어보면 금방 알 수 있다.

 

그 이후 c=n과 임의의 r 을 제공했을 때 받은 값을 우리가 찾고자 하는 c라고 하자.

그러면 우리는 이 값으로 만들 수 있는 r을 찾아줘야 한다.

 

이는 생각보다 간단한데, 어떤 값 r에서 c번 합성해서 c가 나와야 되니, n번에서 c를 빼준 다음, 합성함수를 구해주면 된다. 

즉 {f^(n-c)}(r) 을 구해주면 r에서 c번 합성했을 때 c가 나오는 r을 구할 수 있게 된다.

 

이렇게 하면 대부분의 답을 구할 수 있지만, 반례가 존재하는데, n-c 가 0일 경우이다.

입력의 범위에선 0이 나올 수 없으니 이 경우에는 다르게 처리해줘야 한다.

 

 n-c 가 0이라는 것은 즉, c = n 이라는 소리다.

 

 이런 경우는 어떻게 나올 수 있을까?

 

이 경우에도 2가지가 존재한다.

1. 정의역과 치역이 모두 같은 X 이며, 마지막에 n을 지날 때

2. n에서 사이클이 생길 때

 

앞서 말했듯이, 처음에 c=n 을 제공한다면 어떤 값이든 최소 한번 이상의 사이클을 가지게 된다.

그러므로 n번의 합성을 통해 n이 나왔다는 것은 사이클의 크기가 n이거나, 어디선가 사이클이 반복되기 시작하면서 n으로 수렴하게 된 2가지 경우만이 존재하게 된다.

 

이렇게 2가지의 경우를 알았으니 이에 대한 출력을 해주면 되는데, 조금만 잘 생각해보면 결국 c=n, r=n 이라면 두가지의 조건을 모두 충족한다는 것을 알 수 있다.

 

 

추가로 이 문제는 인터렉티브 문제이기 때문에, 인터렉티브를 할 수 있도록 입력을 변환해주어야 하는데, 파이썬의 경우 sys.stdin.readline 을 사용하지 않는다면 input 만으로도 인터렉티브가 가능하다.

 

n=int(input())
print("?",n,1)
v=int(input())
if n-v>0: 
    print("?",n-v,1)
    print("!",v,int(input()))
else:
    print(f"! {n} {n}")