#1494 절대값 수열

절대값 수열 문제는 전체적으로 감소하는 수열의 특징을 이용하시면 됩니다.

 

일반적으로 비율로 줄어드는 수열의 경우에는 그 비율이 $1/\phi$인 경우 가장 오래 갈 수 있습니다.

절대값 수열도 크게 다르지 않기 때문에, 가장 긴 수열을 얻기 위해서는 $1/\phi$ 비율에 가까워야 합니다.  정수에서는 1618:1000 정도의 비율입니다.

 

황금비율

 

이 문제는 Platinum I 문제이지만, 수열 법칙을 조금 이해하시면 풀 수 있습니다.

 

60과 1로 시작하는 수열을 생각해보면,

 

60, 1, 59, 58, 1, 57, 56, 1, 55, 54, 1, ..., 2, 1, 1, 0, 1, 1, 0, ....

 

형태로 전체적으로 감소하는 수열이 됩니다.  이 중 두번째 값인 1이 여러번 반복하게 되는데, 이 숫자는 3번에 한번씩 나오는 것을 알 수 있습니다.  만약 첫번째 수가 두번째수보다 꽤 큰 수라고 하면, 두번째 수를 $v$라고 했을 때, 첫번째 수를 $kv+\alpha$로 표현할 수 있습니다.

$$kv+\alpha ,v,(k-1)v+\alpha ,(k-2)v+\alpha ,v$$

가 되어서 3번만에 $2v$만큼 첫번째 수가 줄어듭니다.

 

여기서 첫번째 수를 $u$, 두번째 수를 $v$라고 했을 때, $u>=2v$ 조건을 만족한다면, 3번후의 값을 알 수 있고, 그 조건이 만족하는한 계속 진행할 수 있습니다.  $\frac{u}{2v}$ 횟수만큼 반복할 수 있으므로, 이걸 이용하면 많이 줄일 수 있습니다.

 

만약 $u<2v$라고 한다면, 우리는 점화식 그대로 적용하면 됩니다.  상당히 빠르게 감소하게 되고, 그 비율은 $O(\log min(first,second))$ 로 놓을 수 있습니다.  왜냐하면 수 하나가 0이 되는 순간이 $O(\log min(first,second))$ 이내에 발생하게 되기 때문입니다.  수 하나가 0이 되면, 그 다음부터는 진동하게 됩니다.  3, 0인 경우 3, 0, 3, 3, 0, 3, 3, 0, ... 형태로 진동하죠.  이 경우는 $u>=2v$ 조건에 부합하므로 결국 같은 방식으로 처리할 수 있습니다.

 

그래서 전체적으로 $O(\log min(first,second))$ 알고리즘으로 문제를 풀 수 있습니다.