728x90
시간 제한 2초, 메모리 제한 256MB
# 문제
- 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다.
- 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
- 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N이 주어진다.
출력
- 첫째 줄에 조건을 만족하는 수를 출력한다.
# 접근 방법
- 우선 소수를 구해주었다.
- 이 때 주의할 점은 100001까지가 아닌, 1000000보다 크거나 같은 소수 중 팰린드롬인 수까지 구해야 하므로 여유있게 1500000까지 구해주었다.
- 이후, bisect를 이용하여 N이 들어갈 index를 구해서 해당 index 부터 팰린드롬인 수를 찾을 때까지 for문을 돌려주었다.
import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from bisect import bisect_left
N = int(input())
nums = []
check = [True] * 1003002
for i in range(2, 1003002):
if check[i] == True:
cnt = 2
while i * cnt < 1003002:
check[i*cnt] = False
cnt += 1
for i in range(2, 1003002):
if check[i] == True:
nums.append(i)
idx = bisect_left(nums, N)
for i in range(idx, len(nums)):
val = str(nums[i])
left, right = 0, len(val) - 1
flag = True
while left <= right:
if val[left] != val[right]:
flag = False
break
left += 1
right -= 1
if flag:
print(nums[i])
break
728x90
'ALGORITHM > 정렬, 탐색,구현' 카테고리의 다른 글
[백준 2115번] 파이썬 - 갤러리 (0) | 2024.05.29 |
---|---|
[백준 16508번] 파이썬 - 전공책 (0) | 2024.05.12 |
[백준 - 2559번] 파이썬 - 수열 (1) | 2024.04.28 |
[코드트리] 파이썬 - 고대 문명 유적 탐사 (1) | 2024.04.20 |
[코드트리] 파이썬 - 나무 타이쿤 (0) | 2024.04.13 |