https://programmers.co.kr/learn/courses/30/lessons/12923
-
flow
처음에 문제를 봤을 때 소수와 관련이 크다고 생각을 했다. 자세히 보다보면 규칙을 찾을 수 있는데 소수인 index는 값이 1이 되고, 합성수들은 약수 중 가장 작은 소수로 나눠진 값을 가진다. 길이와 블록 수가 달라서 이를 유의하면서 조건을 추가하면 정답을 찾을 수 있다. 그런데 문제가 정확하지 않은 지, 오히려 조건을 추가했을 때, 채점 정답이 안 나오는 걸 경험할 수 있다. 반대로 조건을 빼보면 정답은 다 맞지만 효율성 테스트 즉, 시간초과가 나게 된다. 시간 복잡도가 O(N^(3/2)) 라 괜찮을 거라 생각했는데 좀 더 효율적으로 짜는 방법이 있는 것 같다. 조금 더 고민해보다가 문제 조건이 꺼림찍해서 일단 패스했다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A12923.py
