강의로 돌아가기
효율성 테스트 "실패" 원인 분석 및 해설.
효율성에서 시간초과도 아니고 실패를 때리다니..
참 재밌는 문제입니다.
이 문제는 아주 단순한 문제입니다.
쉽게 생각하면 약수를 찾는 문제입니다.
그것도 자신자신을 제외한 약수 중에서 가장 큰 약수를 찾는 문제입니다.
뭐 다르게도 해석할 수 있겠지만, 저는 2번째 부터 블럭을 설치한다는 점이다.
n * i (n은 현재 블록, i는 배수, i = 2 부터 시작함.) 와 같은 조건을 가지고 블록을 새로 갱신한다는 점에서,
자기 자신을 제외한 가장 큰 약수를 구하는 문제라는 것을 알았습니다.
아마 직접 하나씩 연산해보시면, 이해가 되지 않을까 싶습니다.
예를 하나 들면, 10번 위치에 어떤 블럭이 올 수 있을가요?
적어도 배수를 하여 10을 만들 수 있는 블럭 중에 가장 최근에 설치된 블럭이어야 합니다.
하지만 정작 10 본인은 처음 설치시 10 * 2 = 20번째 위치부터 설치되므로, 자기자신은 설치가 불가능합니다.
그러면, 10을 만들 수 있는 배수 중에서 가장 최근에 설치할 수 있는 블럭이라면,
당연히 5밖에 없겠죠? 10자리에는 = 1, 2, 5 블럭이 순차적으로 설치되어 갱신됩니다.
세 수의 공통점은 10의 약수라는 부분이죠. 우리는 10의 약수 중에서 10을 제외한 가장 큰 약수인 5를 구하는 방법을 알면 됩니다.
나눗셈해서 나머지가 0이 되는 지점을 찾아내면 약수를 구할 수 있습니다.
레벨2의 "소수찾기"의 문제에서 업그레이드 된 버전입니다.
즉, 해당 문제는 약수를 찾고, 답을 제출하면 됩니다.
약수를 효율적으로 구하는 연산이 필요할겁니다.
가장 대표적으로는 약수를 구할 때, 나누는 수를 현재 수의 제곱근까지만 나누어 보는겁니다.
실질적으로 약수는 제곱근을 넘는 수 중에는 자기자신밖에 존재하지 않기 때문에 가능한 방법입니다.
그리고 효율성 테스트에서 실패하는 이유는,
사용이 가능한 블럭이 10,000,000번 까지 이기 때문입니다.
여기서 반례의 케이스가 발생합니다. 자기자신을 제외한 최대 약수가 10,000,000을 넘는다면,
해당 블럭은 사용하면 안되는 블럭입니다. 그러므로 해당경우에는 그 다음으로 큰 최대 약수를 다시 찾아 블록을 끼워넣어주면 됩니다.
참쉽죠?
자기자신을 제외한 최대약수가 10,000,000이 넘지 않을거라는 착각을 이용해,
문제를 교묘하게 잘 만들어냈습니다.
저도 처음에는 문제의 지문이 잘못된 줄 알았지만..
문제를 풀어보니, 제 머리가 잘못되었다는 것을 느꼈습니다.
보는 사람은 많이 없겠지만, 20000할게요
-
도대체가 효율성 테스트가 예외도 아니고 왜 실패도 뜨는지 엄청 의아하고 고민이 많이 됐는데.... 발견한 것도 대단하시네요
강동희―2022.07.13 21:11
-
역시 문제를 잘읽어야 되는군요 문제를 대충봐서 최대도로랑 최대블록이 같다고 생각했는데..
soypabloo―2022.08.19 12:52
-
제시한 분석과 해설이 효율성 통과에 많은 도움이 되었습니다. 다만 최대약수가 10,000,000를 넘는 경우 그 다음으로 큰 최대 약수를 넣는다고 하셨는데, 그 다음의 최대약수가 없거나 그 약수도 10,000,000넘는 경우에는 1을 넣어야 해결이 됩니다. 1을 제외한 모든 약수가 10,000,000보다 큰 경우가 있다는 것과 이 경우에는 1 블럭이 깔린다는 것을 고려하여 효율성이 통과이 되었습니다.
grasyz―2022.08.31 18:09
-
grasyz님의 말도 맞는 말입니다. 하지만 위와 같은 알고리즘을 사용하여도 같은 결론에 도달함을 알 수 있습니다. 자기 자신을 제외한 최대 약수가 10,000,000이 넘는다면 그 다음으로 큰 약수를 구하면 됩니다. 1은 모든 수의 약수이므로 조건에 부합하지 않을 경우 최종적으로는 1이 구해지는 것을 알 수 있습니다. 또한 약수를 판별할 경우 약수의 대칭성을 이용하여 약수를 높은 수부터 탐색할 수 있습니다.
전현서―2022.09.01 13:10
-
저는 어떤식으로도 통과가 되지 않는데 제 코드에서 잘못된 부분 지적해주실 수 있을까요? 여기 질문하기에 올렸습니다.
JandB―2022.10.04 11:02
-
감사합니다 ~ 저도 문제를 잘못 이해했군요 덕분에 해결했습니다
장대준―2023.01.03 17:21
-
덕분에 해결할 수 있었습니다... 감사합니다!
Sckroll―2023.01.30 18:17
답변 쓰기