[Baekjoon] 1747_소수&팰린드롬

Silver I

문제(출처: https://www.acmicpc.net/problem/1747)

---

<소수&팰린드롬>

문제 

 

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

 

 

입력

 

첫째 줄에 N이 주어진다.

 

 

출력 

 

첫째 줄에 조건을 만족하는 수를 출력한다.

 

 

문제 풀이

   - my solution (Python)

if __name__=='__main__':
    arr=[True]*2000000
    line=int((2000000)*0.5)
    arr[1]=False

    n=int(input())

    for i in range(2, line+1): # 소수 판별
        if arr[i]==True:
            for j in range(i+i, 2000000, i):
                arr[j]=False

    flag=False
    for i in range(n, 2000000):
        cnt = 0
        if arr[i]==True: # 소수이면
            i = str(i)
            for j in range(len(i)//2): # 팰린드롬
                if i[j]==i[len(i)-1-j]:
                    cnt+=1
                else:
                    break
            if cnt==len(str(i))//2:
                print(i)
                flag=True
                break
        if flag==True:
            break

 

 

에라토스테네스의 체를 활용하여 소수를 판별해줍니다. 그다음 N보다 크거나 같은 수 중 소수라면 팰린드롬인지 확인해줍니다.

팰린드롬이라면 그 수를 출력해준 후 종료합니다.

 

• N 입력
• 에라토스테네스의 체를 사용하여 소수 판별
• N보다 크거나 같은 값 중 팰린드롬 확인 -> 팰린드롬이라면 값 출력 후 종료

 

간단한 문제였지만 왜 이렇게 많이 틀렸는가?

 

❓ 틀린 이유는?

1. N 입력이 1000000이라고 했으므로 출력 값으로는 1000000 이상의 값이 나올 수 있다. 하지만 처음에 구현한 코드에서 에라토스테네스의 체를 사용하기 위해 범위를 1000000으로 설정하여 틀렸던 것이다. 

 

2. 문제에서 'N보다 크거나 같고'라고 한 부분을 놓쳤기 때문이다. N보다 큰 값을 구하도록 코드를 구현하였으므로 틀렸던 것이다.

 

3. 1을 입력값으로 넣었을 때 1이 나오면 안 된다. 1은 소수가 아니기 때문이다. 1을 소수가 아닌(False) 값으로 설정해줘야 한다.

 

위와 같이 3개의 문제점을 고쳤더니 문제를 해결할 수 있었다.

 

---

생각🤔

 

---