이상한 카운터 | 설명이 포함된 Hackerrank 문제 해결 방법

문제 설명

이상한 카운터가 있습니다. 처음 1초에 숫자를 표시합니다. 매초 표시되는 숫자는 1에 도달할 때까지 1씩 감소합니다. 다음 초에 타이머는 이전 주기의 초기 숫자의 2배로 재설정되고 카운트다운을 계속합니다. 아래 다이어그램은 처음 세 주기의 각 시간 t에 대한 카운터 값을 보여줍니다.



시간 t에서 카운터에 표시된 값을 찾아 인쇄하십시오.

입력 형식
단일 정수, t의 값.

샘플 입력
4

샘플 출력
6

질문 링크: https://www.hackerrank.com/challenges/strange-code/problem

솔루션(Python3)

def strangeCounter(t):
    # Write your code here
    n = math.log(((t + 3) / 3), 2)
    if math.floor(n) == math.ceil(n):
        return 1
    n = int(math.ceil(n))
    term = 3 * (math.pow(2, n) - 1)
    return int(term - t + 1)

설명

주어진 문제 설명에서 다음을 명확하게 볼 수 있습니다.

첫 번째 사이클을 완료하는 데 걸리는 시간: 3초
두 번째 사이클을 완료하는 데 걸리는 시간: 6초
세 번째 사이클을 완료하는 데 걸리는 시간: 12초

등등.

조금만 관찰하면 주기에 걸리는 시간이 시리즈를 형성하고 있고 그 시리즈가 G.P에 있음을 알 수 있습니다. (기하학적 진행) 공통 비율이 2인 경우.

주기가 끝나는 시간은 해당 주기까지 주기를 완료하는 데 걸린 모든 시간의 누적 합계임이 분명합니다. 즉.

1주기가 끝나는 시간: 3
주기가 끝나는 시간: 첫 번째 주기를 완료하는 데 걸리는 시간 + 두 번째 주기를 완료하는 데 걸리는 시간 = 3 + 6 = 9

등등.

이 시리즈가 G.P. 그런 다음 누적 합계, 즉 모든 주기의 종료 시간은 아래 공식을 사용하여 계산할 수 있습니다.

S = a(rⁿ-1)/(r-1),

여기서 S는 급수의 합, a는 급수의 첫 항, r은 공비, n은 급수의 항 수입니다.

여기, 문제에서 급수의 합(즉, 이 경우 t)이 주어지고, 첫 항과 공비(즉, 3과 2)를 알고 있습니다. 따라서 n을 계산해야 합니다. 위 공식을 사용하여 다음을 추론할 수 있습니다.

n=log₂((S+3)/3)

n으로 정수를 얻으면 주어진 t는 주기의 종료 시간입니다. 그러나 우리가 부동 숫자를 얻는다면 t는 이전 주기의 종료 시간과 다음 주기 사이의 시간입니다. 이때 t의 ceil값과 Sum of G.P.의 공식을 이용하면 된다. 현재 주기의 종료 시간, 예를 들어 용어를 계산할 수 있습니다. 항과 t의 차이가 우리의 답입니다.