[Implementation] Strange Counter

밥은 신기한 카운터를 가지고 있다. 이 카운터는 처음에는 숫자 3을 나타내고, 각 초마다 1이 될 때까지 1씩 감소한다. 1이 되고난 후에는 3에 2를 곱한 값이 6이 되고, 또다시 각 초마다 1이 될 때까지 감소한다.

시간(t)가 주어졌을 때 t초 후에는 카운터에 어떤 숫자가 나타날지 알아내야 한다. 각각의 time배열과 value 배열은 같은 쌍배열 내에서는 그 합이 일정하다. 주어진 그림의 맨 왼쪽은 4로 일정하고, 가운데는 10, 오른쪽은 22로 일정하다. 그리고 이 합은 이전 합에 현재 쌍배열의 value[0]을 더한 값과 같다. 예를 들어, 가운데를 현재 쌍배열이라고 한다면, 이 쌍배열 각 인덱스끼리의 합은 10(4+6, 5+5...)으로 일정하다. 이전 합은 4이고, 현재 쌍배열의 value[0]은 6이다. 4 +6 = 10으로 동일한 것을 알 수 있다.

 

어느 쌍배열에 t가 위치하는지를 알아야 하는데, 이는 t가 어느 합 이상인지를 알아내면 된다. 가운데 쌍배열에서 time[0]은 4로, 이전 쌍배열의 합(1+3 =4, 2+2 = 4, 3+1 = 4) 이상이다. 반대로, 4는 다음 쌍배열의 합(10 + 12 = 22, 11+11 = 22,...)보다 작다.

 

맨 처음 쌍배열의 합은 4이므로 쌍배열의 합을 뜻하는 sum을 4로 초기화하고, sum이 t 이하일 경우에는 다음 쌍배열로 넘어가기 위해 sum을 증가시켜야 하므로 두번째 쌍배열의 value[0]인 6으로 초기화한다. while문으로 t가 sum 이상인 동안 sum에 initial을 더하고 initial에 2를 곱한다. 어느 순간 t가 sum보다 작게 되면 t는 sum에 해당하는 합을 가진 쌍배열에 속하게 되는 것이다. 이 sum에서 t를 빼면 해당 value 값을 알아낼 수 있다.