https://www.acmicpc.net/problem/29728
29728번: 실버와 소수는 둘다 S로 시작한다
브실이는 실버 난이도의 소수 관련 문제를 풀던 도중, "실버"와 "소수"가 동일하게 S로 시작한다는 것을 깨달았다. 물론 소수는 한글로 적었을 때의 발음만 S로 시작하지, 영어로는 prime이라 틀린
www.acmicpc.net
소스코드
풀이
★ 시간초과로 엄청 많이 틀렸던 문제입니다 ! 조건에 주어진대로 잘 구현한 거 같은데 시간초과가 계속 뜨길래 뭐가 잘못됐나 싶었는데 소수를 찾는 과정, 에라토스테네스 체를 쓰는 방식이 조금 달라서 그랬던 거 같습니다 !
★ 먼저 이 문제는 입력 값이 5,000,000까지 들어오지만 제한 시간이 0.2초밖에 되지 않기 때문에 무조건 에라토스테네스 체를 활용하여 소수를 판별해줘야 합니다 ! 보통 구현할 때 이중 반복문으로 소수를 찾아내는 방식이 일반적인 거 같은데, 그 방법대로 하니까 시간초과가 뜨더라구용 ㅠ 그래서 같이 첨부하는 사이트의 방식대로 에라토스테네스를 구현하시는 연습을 하면 좋을 거 같습니다 !
★ 문제의 조건에 소수인 경우 마지막 문자가 'B'인지 아닌지에 따라 문자열을 뒤집어 줘야 합니다. n이 커질수록 문자열도 커질텐데 계속해서 뒤집는다면 그만큼 시간을 사용하기 때문에 자료구조 '덱'과 flag 변수를 사용하여 flag가 True인 경우 뒤에서, False인 경우 앞에서 작업하도록 했습니다.
★ 그 외에 조건들은 그대로 구현해주시면 됩니다 :) 아 그리구 python으로 실행하면 시간초과가 뜨더라구요ㅠ pypy로만 전 통과했습니당 !!
★ 에라토스테네스 체 참고자료
https://freedeveloper.tistory.com/392
[이것이 코딩 테스트다 with Python] 38강 에라토스테네스의 체
https://www.youtube.com/watch?v=9rLFFKmKzno&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=38 다수의 소수 판별 하나의 수에 대해서 소수인지 아닌지 판별하는 방법을 알아보았다 하지만 특정한 수의 범위 안에 존재하
freedeveloper.tistory.com
'Algorithm > 2023 브실컵' 카테고리의 다른 글
| [백준 알고리즘] 29714번: 브실이의 구슬 아이스크림 (Python) (2) | 2023.11.09 |
|---|---|
| [백준 알고리즘] 29730번: 임스의 데일리 인증 스터디 (Python) (1) | 2023.11.09 |
| [백준 알고리즘] 29732번: Rick-Roll Virus (Python) (0) | 2023.11.09 |
| [백준 알고리즘] 29718번: 줄줄이 박수 (Python) (0) | 2023.11.08 |
| [백준 알고리즘] 29723번: 브실이의 입시전략 (Python) (0) | 2023.11.08 |