https://www.acmicpc.net/problem/30826
문제요약
- 펠린드롬 수를 순서대로 늘어놓을 수 있음(첫자리가 0이면 안됨)
- k 번째 숫자를 찾는 문제(k번째 펠린드롬이 아님)
- 문제 예시 참고
접근법
- 보통의 k 번째 수 찾는 방법과 유사하게 접근
- 하나씩 찾지 않고, 큰 단위부터 작은 단위로 쪼개가면서 적당히 skip 하는 방법
- 길이가 n인 펠린드롬의 개수는 알 수 있음
- 길이 n = 0을 포함하는 길이 n - 2의 개수 * 9(= 1 ~ 9)
- 범위를 좁힘 - 구하려는 곳의 펠린드롬의 길이
- k 가 주어지면 어떤 길이의 펠린드롬에 속하는지 구할 수 있음
- 길이가 1인것부터 길이 * 개수 를 빼보면 됨
- k도 변함
- 범위를 좁힘 - 길이 n인 펠린드롬중 어떤 숫자인가
- 1 ~ 9 로 시작하는 길이 n인 펠린드롬의 개수를 알 수 있음 => 개수 * n을 이용해서 k를 줄임
- 두번째 숫자가 0 ~ 9로 구성되어잇는 길이 n인 펠린드롬의 개수를 알 수 있음 => 마찬가지
- 진행하다 보면 최종 펠린드롬과 줄어든 k를 구함 => 그 펠린드롬에서 k 번째가 구하고자 하는 답
newbieski