Dalin's Archive

문제 보러가기!! N 자리 신기한 소수를 찾는 문제이다. 신기한 소수란, 왼쪽에서부터 첫째자리만 봐도 소수이고, 첫째 둘째 자리를 봐도 소수이고, 1-3자리를 봐도 소수이고, ... 1-N자리를 봐도 소수인 수이다. 예를 들어서, 2393은 2도 소수, 23도 소수, 239도 소수, 2393도 소수이다! N은 최대 8이니까 크기가 9인(0번째 인덱스는 편의를 위해서 안 씀) 2차원 리스트를 만들었다. 1 자리 신기한 소수는 쉽게 구할 수 있으니 미리 구해서 첫번째 리스트에 넣었다. 2, 3, 5, 7 그 이후부터는 N자리 신기한 수까지 차례 차례 신기한 수를 찾았다. 방법은 다음과 같다. 2자리 신기한 소수를 찾으려면 왼쪽에 1자리 소수를 두고, 오른쪽에 한자리 수를 붙인 뒤에 그 수가 소수인지 확인하면..

N=int(input()) L=[0]*1003002 #조건에서 N 최댓값이 1000000이라고 함. 그 이상 소수이고 펠린드롬 만족하는 가장 작은 수가 1003001임. L[1]=1 #N 미만의 소수를 구함 for i in range(2,N): if L[i]==0: for j in range(i,1003002,i): L[j]=1 #N이상 for k in range(N,1003002): if L[k]==0: #j가 소수라면 if str(k)==str(k)[::-1]: #펠린드롬인지 체크 print(k) break else: for l in range(k,1003002,k): L[l]=1 에라토스테네스 체 방법으로 소수 구하는 것 공부한 후에, 관련된 문제 풀어보고 싶어서 풀었다~ L=[0]*1003002 ..

문제 보러 가기! 접근 💚 처음에는 소수가 나와서 어떻게 접근할지 고민했다. 우주 생명체 수 N에서 핑거 스냅으로 할 수 있는 4가지 일을 하고, 그게 A와 B 사이의 소수인지 매번 확인하는 것은 힘들 것 같았다. (매번 소수인지 쭉 계산을 해야 하니까.) 그래서 좀 생각을 바꿔봤다! A, B는 100000 이하니까 10만 이하의 소수를 모~두 구하는 것이다. (에라토스테네스의 체로 구했다.) 그리고 A 이상 B 이하의 소수들을 리스트에 저장해두고, 핑거 스냅으로 4가지 일을 한 후에 그 우주 생명체 수가 그 리스트의 값들 중에 있는지 보는 것이다. 최소 몇 번의 핑거 스냅을 해야 할지 구하는 것! 즉 최단 거리를 구하는 것과 같으니까 BFS로 풀었다. 4가지 일을 한 후의 우주 생명체 수를 보고 범위 ..