문제 링크
1. 아이디어
두 자연수의 곱이 n이 되는 순서쌍 $(a, b)$의 개수를 구하는 문제다. $a$가 정해지면 $b = n / a$도 함께 정해지므로, 곱이 n이 되는 $a$는 결국 n의 약수여야 한다. 즉 구하는 순서쌍의 개수는 n의 약수 개수와 같다.
가장 단순한 방법은 1부터 n까지 모든 정수 i에 대해 n이 i로 나누어떨어지는지 확인하며 약수 개수를 세는 것이다. n이 크지 않아 해당 방법으로 충분히 해결할 수 있다.
좀 더 효율적인 방법은 약수의 대칭성을 활용하는 방법이다. 약수는 $\sqrt{n}$을 기준으로 $\sqrt{n}$보다 작은 수와 큰 수가 대칭적으로 나타난다. 따라서 $1$부터 $\sqrt{n}$까지 n이 i로 나누어질 경우(i, n / i) 2개씩 쌍을 세는 방식으로 탐색량을 줄일 수 있다. 이때 i와 n / i가 일치하는 경우 중복으로 카운팅이 되는 점만 주의하면 된다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 완전 탐색 | $O(N)$ | $O(1)$ |
| 제곱근까지 탐색 | $O(\sqrt{N})$ | $O(1)$ |
($N$ = 입력값 n)
3. 코드
풀이 1: 완전 탐색 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
| class Solution {
public int solution(int n) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) cnt++;
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| #include <bits/stdc++.h>
using namespace std;
int solution(int n) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) cnt++;
}
return cnt;
}
|
1
2
| def solution(n):
return sum(n % i == 0 for i in range(1, n + 1))
|
풀이 2: 제곱근까지 탐색 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int solution(int n) {
int cnt = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
cnt++;
if (i != n / i) cnt++;
}
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <bits/stdc++.h>
using namespace std;
int solution(int n) {
int cnt = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
cnt++;
if (i != n / i) cnt++;
}
}
return cnt;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| import math
def solution(n):
cnt = 0
for i in range(1, math.isqrt(n) + 1):
if n % i == 0:
cnt += 1
if i != n // i:
cnt += 1
return cnt
|