728x90
반응형
문제:
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 N이 주어진다.
출력:
첫째 줄에 조건을 만족하는 수를 출력한다.
풀이방법:
소수를 판정하는 알고리즘 중 에라토느테네스의 체와 팰린드롬 알고리즘을 함께 사용하는 알고리즘이다. N으로 들어올 수 있는 가장 큰 숫자인 1,000,000에 해당하는 답은 1003001이라는 사실을 사용해서 그 만큼을 sosu 리스트를 초기화했다. (혹은 넉넉하게 큰 길이로 초기화해도 된다.) 이 sosu 리스트를 에라토스테네스의 체를 사용해서 소수만 남겨둔다.
이후 while 반복문을 통해서 sosu이면서 팰린드롬인 경우에 그 숫자를 출력하고 break를 통해 정지시키면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def checkpen(m):
temp = str(m)
for i in range(len(temp)//2):
if temp[i]!=temp[len(temp)-i-1]:
return False
return True
N = int(input())
sosu = [True]*1003002
sosu[0],sosu[1]=False,False
for i in range(2,len(sosu)):
if sosu[i]:
for j in range(2*i,len(sosu),i):
sosu[j]=False
while True:
if sosu[N] and checkpen(N):
print(N)
break
N+=1
|
cs |
문제링크:
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]11060. 점프 점프 (0) | 2020.12.03 |
|---|---|
| [BOJ]10835. 카드게임 (0) | 2020.12.01 |
| [BOJ]1707. 이분 그래프 (0) | 2020.11.24 |
| [BOJ]7562. 나이트의 이동 (0) | 2020.11.19 |
| [BOJ]1992. 쿼드트리 (0) | 2020.11.17 |