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

자가 복제 문자열

 

풀이

문제를 보고 문제에서 원하는 방향대로 해서 f함수와 g함수를 만들고 그것을 문제에서 제공한 풀이법 대로 풀어서 아래처럼 만들었다.

# Pn을 구하기 위함 함수
def p_time(K):
    length_n = 1
    n = 0
    # 길이가 K보다 작을때만
    while length_n < K:
        n += 1
        length_n = length_n + 1 + length_n
    return n

# 문자 반전
def f(A):
    tmp_A = ""
    for i in range(len(A)):
        if A[i] == '0':
            tmp_A += '1'
        else:
            tmp_A += '0'
    return tmp_A

# 문자열 좌우 반전
def g(A):
    reverse_A = ""
    for j in range(len(A)-1,-1,-1):
        reverse_A += A[j]
    return reverse_A


T = int(input())
for testcase in range(1, T+1):
    K = int(input())
    P = '0'
    # 몇 Pn을 하고 나서 K를 구할 수 있는지 확인
    n = p_time(K)
    # n 번 동안 진해서 P를 생성해낼 것
    for _ in range(n):
        P = P+'0'+f(g(P))
    print(f'#{testcase} {P[K-1]}')

문제는 풀리지만, 시간초과가 나버리는 바람에 제대로 풀 수는 없었다.
결국 찾고 찾아 아래처럼 풀었다.

복제 과정에서 생성되는 문자열의 패턴을 파악하여 문제를 해결하는 방법이다.
이 방법으로 먼저 푼 사람은 진짜 대단한 사람인가보다. 어떻게 이런 생각을 하지????

우선 K를 제대로된 인덱스로 사용하기 위해 입력받으면서 -1을 해주었다.
그리고 K가 홀 수 라면 (k-1)//2 해준 값을 다시 k로 잡는 방식을 반복해 주고, 짝수가 되었을 때, k%4 == 0이면 0을, k%4가 0이 아니면 1을 출력하게 했다.

설명을 덧붙이면 우선 P는 아래처럼되어있다.

P1 = "001"
P2 = "0010011"
P3 = "001001100011011"
P4 = "0010011000110110001001110011011"

이를 보면 항상 앞선 Pi-1의 값을 그대로 적용하고 뒤에 추가적으로 문자열이 붙어있는 것을 확인할 수 있고, 또한 이에 따라 문자열이 아주 길게 늘어졌을 때의 K번째 숫자 또한 항상 동일함을 추측할 수 있다.

현재 K는 0에서 시작하지만 1이 0처럼 사용되고 있다.
여기서 발견할 수 있을지 모르겠지만, 1부터가 아닌 0부터 시작하는 것처럼 K를 사용한다면
P4를 예시로 보게 되면
0
0100
1100
0110
1100
0100
1110
0110
11
항상 4의 배수 인덱스는 0을 가지고 %4 == 2는 1을 항상 가지는 것을 확인할 수 있다. 그 외 홀수 번째는 0과 1을 반복하고 있는 것을 눈으로 확인할 수 있다.
이를 이용한 풀이가 아래가 되겠다.

T = int(input())
for testcase in range(1, T+1):
    k = int(input()) - 1
    while k % 2 == 1:
        k = (k - 1) // 2
    if k % 4 == 0:
        print(f'#{testcase} 0')
    else:
        print(f'#{testcase} 1')