Dalin's Archive

1년 전에 틀렸던 문제를 풀어봤다. 이번에는 과거의 나에게 알려주는 말투로 적어보려고 한다. ㅎㅎ 만우절이니까..ㅎㅎ 문제 보러 가기 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 안녕! 베르트랑 공준 문제구나. 와 저런 수학적인 명제가 있다니 정말 놀랍네. 음 이 문제는 뭐가 포인트일까? 맞아 맞아~ 소수를 구하는 게 포인트겠지~ 너는 어떻게 풀었는지 볼까? while True: n=int(input()) if n == 0: exit() for i in range(n+1,2*n+1): if n==1..

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