[백준] 30826번 그 긴 수

https://www.acmicpc.net/problem/30826

30826번: 그 긴 수

 

 

 

Ad Hoc 문제, 저번의 거울 숫자 문제와 비슷한가? 싶어서 건드려 보았는데, 그냥 각 경우를 고려해서 잘 짜주면 된다.

 

- 문제 요약

팰린드롬 수를 순차적으로 계속 붙여나간 수에서 K 번 째 위치한 수를 찾아주면 된다.

Ex. 12345678911223344556677 ... 

 

- 각 자리 수 마다 팰린드롬 수를 만들 수 있는 경우의 수

한자리 수의 경우 9 가지 (1, 2, 3, 4, 5, 6, 7, 8, 9)

두자리 수의 경우 9 가지 (11, 22, 33, 44, 55, 66, 77, 88, 99)

세자리 수의 경우 9 * 10 가지 (101, 111, 121 ... 202, 212, ... ,999)

네자리 수의 경우 9 * 10 가지 (1001, 1111, 1221, ... 2002, 2112, ... , 9999)

...

즉 연산을 통해 각 구간의 팰린드롬 수의 개수를 구할 수 있다.

 

 

만약, 다음 번 재귀가 K를 넘어간다면,  현재까지 진행된 index로부터 K 번째에 해당되는 팰린드롬 수를 구한다.

K 번째에 해당되는 팰린드롬 수는 다음과 같이 구할 수 있다.

 

tmp = index + odd * length;

n = (K - index) / length;

nl = (K - index) % length;

 

	1	2	3	4
팰린드롬 수의 범위	1 ~ 9	11 ~ 99	101 ~ 999	...
팰린드롬 수 개수 * 팰린드롬 수의 길이	9 개	9 개 * 2	90 개 * 3	...
다음index (tmp)	9	9 + 18 = 27	27 + 270 = 297

 

 

만약 25(K = 25) 번째 숫자를 찾는다면, 25는 11 ~ 99 사이에 존재하고,

n = (25 - 9) / 2 = 8

nl = (25 - 9) % 2 = 1 

즉, 길이가 2 인 팰린드롬 숫자 중 8 번째 숫자의 1 번 인덱스 를 의미하게 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
#include <string>
using namespace std;
long long K;
long long odd = 9;
long long even = 9;
void recursion(int length, long long index)
{
   // cout << index << " ";
    long long tmp;
    if (length % 2 == 1)
    {
        tmp = index + odd * length;
        if (tmp > K)
        {
            long long n = (K - index) / length;
            long long nl = (K - index) % length;
            long long ten = 1;
            for (int i = 0; i < length / 2; ++i)
            {
                ten *= 10;
            }
            string itos = to_string(ten + n);
            string re = itos;
            for (int i = itos.size() - 2; i >= 0; --i)
            {
                re += itos[i];
            }
            cout << re[nl];
            return;
        }
        odd *= 10;
    }
    else
    {
        tmp = index + even * length;
        if (tmp > K)
        {
            long long n = (K - index) / length;
            long long nl = (K - index) % length;
            long long ten = 1;
            for (int i = 0; i < length / 2 - 1; ++i)
            {
                ten *= 10;
            }
            string itos = to_string(ten + n);
            string re = itos;
            for (int i = itos.size() - 1; i >= 0; --i)
            {
                re += itos[i];
            }
            cout << re[nl];
            return;
        }
        even *= 10;
    }
    recursion(length + 1, tmp);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> K;
    recursion(1, 1);
    return 0;
}