[BOJ 14399] 2연산

문제: https://www.acmicpc.net/problem/14399

 

풀이:

X연산을 시행한 이후에는 X>Y, Y연산을 시행한 이후에는 Y>X를 만족합니다.

즉, 최종적으로 만들 두 수가 정해져 있는 경우 가장 마지막 연산부터 X>Y인지, Y>X인지 정해가면서 계산해오면 사용한 연산의 나열을 알 수 있고, 이는 수가 정해져있을 경우 유일합니다. (유클리드 알고리즘을 떠올려도 좋습니다)

 

이제, 모든 1 이상 N이하의 i에 대해서 (N, i)를 만드는 연산 횟수를 세고 (이는 mod연산을 이용해서 개수만 빠르게 세어줍니다), 이 중 연산 횟수가 최소인것을 모두 골라 사전순 최소인 것을 고르면 됩니다. 가능한 길이로는 $O(\log N)$ 상한이 있기 때문에, 위 방법으로 문제를 풀면 $O(N \log N)$ 이 됩니다.

 

*문자열을 naive 하게 뺄셈으로 만드는 방식도 $O(N \log N)$ 시간복잡도인것 같은데 (Harmonic Sum 같은 논리입니다) 확실하지는 않습니다.

 

코드1: https://www.acmicpc.net/source/share/a4760ba638e54ca19e5f82837839404b

코드2: https://www.acmicpc.net/source/share/bd1f6be55a4c485995b5447a10a78e51