search

BurningFalls / burningfalls.github.io

MIT License
2 stars 0 forks source link

algorithm/boj-23820/ #12

Open utterances-bot opened 4 days ago

utterances-bot commented 4 days ago

[BOJ 23820] 백준 23820번 - MEX - LogLife

2021 POSTECH Programming Open Contest H번 - 백준 23820번 MEX 풀이

https://burningfalls.github.io/algorithm/boj-23820/

celbeing commented 4 days ago

선생님 글 보고 도움을 얻어서 한 가지 저도 남겨드리자면 저도 회고에 남기신 방법으로 접근을 시도했으나 실패했습니다. 원인은 12 같은 경우입니다. 소수 세 개 이상으로 합성되는 이런 수는 26 또는 34와 같이 소수 두 개의 곱으로 나타낼 수 없기 때문에 단순 없는 소수만 찾으면 이런 수를 놓칩니다. 아래는 반례입니다. 정답은 8이지만 소수만 찾으면 11이 나옵니다. 6 0 1 2 3 5 7

BurningFalls commented 4 days ago

@celbeing

아하! 소수가 아니지만 소수 세 개 이상의 곱으로 이루어진 합성수도 충분히 답이 될 수 있네요! 4는 22로 만들 수 있고, 6은 23으로 만들 수 있어 답이 되지 않지만, 223=26 혹은 223=43로 이루어지는 12는 4와 6 둘다 없으면 만들 수 없기 때문에 답이 되는군요. 가르쳐주셔서 감사합니다!