약수 - 백준 1037 [Python]
C가 A의 약수라면, A/C도 A의 약수가 되어야 한다. 또 C가 A/C인 경우도 있는데, 이때는 A = C^2이라는 수식이 성립하는 경우이다. 따라서 약수를 구할때, 루트 A를 까지 구한 다음, 모든 약수를 구하여 시간복잡도를 줄일 수 있다. 왜냐하면, A만큼 나누어 보는 것이 아니라, 루트 A까지 약수를 구하기 때문에 O(N) > O(루트N)이 되기 때문이다. Example 1) https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 문제 ..
2021. 7. 15.
단축키
내 블로그
| 내 블로그 - 관리자 홈 전환 |
Q
Q
|
| 새 글 쓰기 |
W
W
|
블로그 게시글
| 글 수정 (권한 있는 경우) |
E
E
|
| 댓글 영역으로 이동 |
C
C
|
모든 영역
| 이 페이지의 URL 복사 |
S
S
|
| 맨 위로 이동 |
T
T
|
| 티스토리 홈 이동 |
H
H
|
| 단축키 안내 |
Shift + /
⇧ + /
|
* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.