[SWEA] 7584. 자가 복제 문자열(python)

📌문제

💪아이디어

최대 n이 1e18이기 때문에 최대 O( $log{n}$ )의 알고리즘으로 짜야했다.

1. 규칙성 찾기
   P는 P + ‘0’ + ^P 의 꼴로 만들어진다. 만들어지는 문자열[i]의 길이는 $ \text{1, 3, 7, 15, … ,}2^{i+1}-1$씩 늘어난다. P[1]부터 문자열을 각 자릿수를 1부터 센다고 하면 4배수자리에 ‘0’이 붙는다.

0	0 1 3 4 7 8 9 12
1	2 5 6 10 11 13 14

$$ f(k) = \begin{cases} 0, & \text{if $4k$} \\ 1, & \text{if $4k+2$} \\ {(k-1)/2} & \text{if $k$ is odd} \end{cases} $$

이러한 규칙성을 찾을 수 있다.

🥂코드

T = int(input()) # 테스트 케이스 수 입력받기
for tc in range(1,T+1): 
    # tc번째 테스트 케이스의 K 입력받기 
    # K번째는 인덱스 K-1
    k = int(input())-1 
    n=0
    while k>=0:
        if k % 2: k=(k-1)//2
        if k % 4 == 0: 
            break
        elif k%2==0:
            n=1
            break
    print('#{} {}'.format(tc,n))