-
[BOJ - 17394] 핑거스냅카테고리 없음 2020. 2. 12. 19:41
https://www.acmicpc.net/problem/17394
17394번: 핑거 스냅
[어벤져스] 시리즈를 보지 않은 사람이라도 ‘인피니티 건틀렛’이 무엇인지는 다들 알 것이다. 그래도 모르는 사람들을 위해 설명을 하자면, 인피니티 스톤이 모두 모인 인피니티 건틀렛을 끼고 손가락을 튕기면, 사용자가 원하는 것을 할 수 있다. 그러나 반동이 매우 심하기 때문에 그리 많이는 사용할 수 없다. 정신 나간 수학자 Sonaht는 우연히 이 인피니티 건틀렛을 손에 넣게 된다. 그러나 이 인피니티 건틀렛에는 약간의 하자가 있어서, 핑거 스냅으로 할 수
www.acmicpc.net
약간.. BFS같지않은 BFS로 문제를 풀었다.
다익스트라로 해도괜찮을법하긴 하지만, 크기가 크지않아서 그냥 BFS로진행했고,
문제를 Solve하기전에, 에라토스테네스의 체로 먼저 소수를 지정하고
제시된 구간안에 소수가없으면 계산할필요없이 바로 답을내고, 아니라면
소수를 찾는 Solve를 실행한다.
Solve는 BFS에서, 노드 Memo중 더 작은 값이 있을때는 다시한번 덮어주는 방식으로 진행했다.
아무래도 2만 곱해나가는것보다, 3을 곱해나가는과정은 생각보다 빠르기떄문에, 시간초과없이
문제를 해결할수있었던것 같다.