첫번째 풀이
약수의 갯수 구하기: O(n)
1~n까지 약수 갯수 체크 : O(n)
으로 O(n^2) 라서 시간초과 이슈 발생
총점 62/100
두번째 풀이
시간 반줄이는 방향으로 약수 갯수 구할때 범위 반쪼개서 한번에 구하는 식으로 변경
결국 O(n/2 * n )이기 때문에 역시 동일하게 시간초과 이슈 발생
총점 67/100
세번째 풀이
- 약수 갯수는 소인수분해 후 각 소수들에 대한 지수+1 의 곱인데, 이를 활용하는 방향 검토
- 소수를 저장해서 이용하는 방향으로 검토
- 소수들에 대해서 1~k 까지 m^n승 모두 찾고 약수 갯수 업데이트 하는 방향 검토
= 여기서 도저히 뭔가 방법이 떠오르지 않음. 약수 갯수 구하는데, O(루트n) 시간 걸릴 것 같은데...
네번째 풀이
- 에라토스테네스의 체 ? 인가 뭔가를 씀.
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수
ko.wikipedia.org
이렇게 하면 소인수분해 되고, 약수의 갯수를 구할 수 있음. 시간복잡도 또한 O(n)보다 작아짐.
총점 100/100
알고리즘 자체로 잘 이해가 안됨. 설명은 내가 세번째 풀이때 의도한 방식이랑 비슷한 결인 것 같은데..
'개발일지 > 알고리즘-문제풀기' 카테고리의 다른 글
| 프로젝트 오일러 Q10 화폐 지불 (미해결) (0) | 2024.05.22 |
|---|---|
| 프로그래머스 - LV1 - 체육복 (1) | 2023.12.20 |
| 프로그래머스 - LV1 - 신규 아이디 추천 (0) | 2023.12.19 |