n번째로 작은 팰린드롬 수를 찾는 놀라운 방법

https://atcoder.jp/contests/abc363/tasks/abc363_d

D - Palindromic Number

 

 

n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다

 

그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다

 

0,1,2,3,4,5,6,7,8,9 >>> 10개

 

11,22,33,44,55,66,77,88,99 >>> 9개

 

101, 111, 121, 131, 141, ... ,191

202,212,222,232,..., 292

303,313,323,..., 393 

...

909, 919,...,999 >>9*10 = 90개

 

1001, 1111, 1221, 1331,..., 1991

...

9009,9119,9229,...,9999 >>> 9*10 = 90개

 

5자리의 경우도 10001을 보면 1번째 자리에 9가지, 2번째, 4번째 자리에 10가지, 3번째 자리에 10가지 들어가서

 

9*10*10 = 900개

 

6자리도 100001을 보면 1번째 자리에 9가지, 2번째, 5번째 자리에 10가지, 3번째, 4번째 자리에 10가지로 900개

 

...

 

1자리는 10개

 

2자리는 9개

 

3자리는 90개

 

4자리는 90개

 

5자리는 900개

 

6자리는 900개

 

...

 

1자리를 제외하고 d자리의 경우 9*(10**((d+1)//2-1)))개 있다는 것을 알 수 있다

 

1자리는 0~10으로 10개 있으므로, 먼저 n이 10이하이면 n-1을 출력하면 된다

 

n이 10보다 크다면 2자리 이상의 팰린드롬 수라는 것을 알 수 있고

 

d = 2부터 1자리씩 올려가면서 n에 10,9,90,90,900,900,...을 차례대로 빼보면서 n이 음수가 될때까지 빼주면

 

n번째 팰린드롬 수가 몇자리인지 알 수 있다

 

예를 들어 n = 46이라 한다면.??

 

d = 2에서 46 - 10 - 9 = 27

 

d = 3에서 27 - 90 < 0이므로, 46번째 팰린드롬 수는 3자리라는 것을 알 수 있다

 

d = 1

n -= 10

while n > 0:

    d += 1

    n -= (9 * 10**((d+1)//2-1))

 

 

이게 무슨 뜻이냐면, 46번째 팰린드롬 수를 찾기 위해, 1자리 팰린드롬 수 10개 제외,

 

2자리 팰린드롬 수 9개 제외하고 3자리 팰린드롬 수 중에 27번째 팰린드롬 수를 찾으면 된다는 뜻이 된다.

 

3자리 팰린드롬 수 중 27번째 팰린드롬 수는 어떻게 찾을 수 있을까?

 

101

111

121

131

141

151

...

202

212

222

232

...

898

909

919

...

999

 

여기서 d = 3일때, 앞 (d+1)//2 = 2자리에 주목해보면 놀랍게도

 

10, 11, 12, 13, 14, 15, 16, 17, ... ,91,92,93,94,95,96,97,98,99가 순서대로 나열되어 있고

 

뒤에 1자리는 이 앞 2자리에서 맨 앞 1자리만 그대로 뒤에 붙여주면 만들 수 있다는 것을 알 수 있다

 

10, 11, 12, 13, 14, 15, 16, 17, ... ,91,92,93,94,95,96,97,98,99에서 27번째 수를 찾으면 된다

 

그것은 36인데, 놀랍게도 10**((d+1)//2-1)에 27-1을 더해주는 것과 같다.

 

그리고 36의 앞 1자리를 뒤에 붙여서 363이 n = 46번째 팰린드롬 수이다.

 

만약 d = 4인 경우를 보면

 

1001

1111

1221

1331

1441

1551

...

9009

9119

9229

9339

...

9999

 

역시 앞 (d+1)//2 = 2자리를 보면 놀랍게도

 

10,11,12,13,14,...,99가 순서대로 되어 있고 여기서 4번째 수를 찾아보면

 

13 = 10**((d+1)//2-1) + 4-1이며 13을 그대로 거꾸로 해서 뒤로 붙이면 1331이다

 

 

따라서 정리하면 n이 10이하이면 n-1이 n번째로 작은 팰린드롬 수

 

n이 10보다 크다면, n에 10,9,90,90,900,900,...을 차례대로 빼서 n이 음수가 되는 순간 멈춘다

 

이는 n에 10을 먼저 빼고, d = 2부터 시작해서 9 * 10**((d+1)//2-1)을 빼며 d를 1씩 증가시키는 것과 같다

 

n이 음수가 되는 순간, 다시 9*10**((d+1)//2-1)을 더해주면 d자리의 n번째 팰린드롬 수를 찾는 것과 같다

 

d자리의 n번째 팰린드롬 수는 앞 (d+1)//2자리가 10**((d+1)//2-1)+n-1이다.

 

그리고 d가 짝수라면 앞 (d+1)//2자리 정수를 그대로 거꾸로 붙여주면 된다(13 + 31)

 

d가 홀수라면 맨 뒤 1자리 제외하고 나머지를 그대로 거꾸로 붙여주면 된다(36 + 3)

 

 

n = int(input())

if n <= 10:
    
    print(n-1)

else:
    
    d = 1

    n -= 10

    while n > 0:
        
        d += 1

        n -= (9 * 10**((d+1)//2-1))
    
    n += (9*10**((d+1)//2-1))
    
    answer = 10**((d+1)//2-1) + n-1

    if d % 2 == 0:
        
        print(str(answer) + str(answer)[::-1])
    
    else:
        
        print(str(answer) + str(answer)[:-1][::-1])

 

 

2. 비슷한 문제

 

29535번: Геном-палиндром (acmicpc.net)

 

A,C,G,T만 사용할 수 있는 모든 길이 n인 팰린드롬 문자열을 사전 순서대로 나열할때, k번째 문자열을 찾는 문제

 

위와 비슷한 원리로 접근하면 된다

 

길이가 1인 경우는 A,C,G,T로 4가지 있다.

 

따라서 5번째 문자열부터는 불가능하다.

 

n,k = map(int,input().split())

answer = ['A','C','G','T']

if n == 1:

    if k <= 4:

        print(answer[k-1])

    else:

        print('Impossible')

 

 

길이가 2부터는 위에서 배운 원리와 비슷하게 앞 (n+1)//2자리가 

 

AAA

AAC

AAG

AAT

ACA

ACC

...

 

이런 식으로 순서대로 되기 때문에 이를 먼저 찾고, 팰린드롬이 되도록 뒤에 그대로 붙여주면 된다는 식으로 찾으면 된다

 

 

근데 이제 문제는 이렇게 나열한 문자열 중에서 K번째 문자열을 찾아야하는데 이게 좀 어렵더라

 

 

예를 들어 앞 3자리만 찾는다고 해보면 가능한 모든 경우는 각 3칸이 A,C,G,T 4가지만 들어갈 수 있으므로

 

4**3 = 64개 있는데, K가 65이상이면 불가능하다.

 

따라서 K가 64이하인 경우에만 팰린드롬 문자열이 존재하고

 

AAA  1

AAC  2

AAG  3

AAT  4

ACA  5

ACC  6

...

 

여기서 1,2,3,4,5,6,...을 3자리 4진법으로 바꿔보면 

 

001

002

003

010

011

012

...

 

이렇게 하면 1이면 A, 2이면 C, 3이면 G... 이렇게 접근했는데.. T가 문제더라고...

 

그래서 ChatGPT한테 물어봤더니 K -= 1로 해서 zero index로 하면 놀랍게도 해결되더라

 

AAA  0

AAC  1

AAG  2

AAT   3

ACA  4

ACC  5

...

 

이 상태에서 3자리 4진법으로 바꿔보면

 

000

001

002

003

010

011

...

 

이러면 0은 A, 1은 C, 2는 G, 3은 T로 바꾸면 된다

 

그리고 나서 전체 길이가 홀수라면 맨 뒤 1자리 제외하고 나머지를 거꾸로 그대로 붙이면 될 것이고

 

전체 길이가 짝수라면 그냥 거꾸로 그대로 붙이면 되는 것

 

n,k = map(int,input().split())

answer = ['A','C','G','T']

if n == 1:

    if k <= 4:

        print(answer[k-1])

    else:

        print('Impossible')

else:

    d = (n+1)//2

    if k > 4**d:

        print('Impossible')

    else:

        str_list = ['A']*d
        chr_list = ['A','C','G','T']

        k -= 1

        four = []

        while k > 0:
            
            p,q = k//4,k%4
            four.append(q)
            k = p
        
        while len(four) != d:
            
            four.append(0)
        
        for i in range(len(four)):
            
            str_list[d-1-i] = chr_list[four[i]]
        
        answer = ''.join(str_list)

        if n % 2 == 0:

            print(answer + answer[::-1])

        else:

            print(answer + answer[:-1][::-1])