https://www.acmicpc.net/problem/24456
1부터 $NM$까지의 모든 수에 대해 해당 수를 두 수의 곱으로 표현하는 모든 경우를 구하는 문제라고도 생각할 수 있습니다. 단순히 모든 약수를 확인한다면 $\mathcal{O}({(NM)}^2)$의 시간이 걸릴 것이라고 생각했고 커팅하는데 시간이 걸렸습니다.
커팅은 소인수분해를 하듯이 하면 됩니다. $x$의 약수를 확인할 때 $\sqrt{x}$까지의 수로 나누어지는지만 확인하면 두 수의 곱으로 표현하는 모든 경우의 수를 확인할 수 있습니다. $\sqrt{x} \times \sqrt{x}$은 항상 $x$보다 크기 때문입니다.
아래는 코드입니다.
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
using namespace std;
int T, n, m, k;
int32_t main(void) {
FastIO;
T = 1;
//cin >> T;
while (T--) {
cin >> n >> m >> k;
int cnt = n * m;
int diff = abs(n - m);
int ans = 0;
while (cnt > 1) {
cnt--;
int flag = 0;
for (int i = 1; i * i <= cnt; i++) {
if (cnt % i) continue;
int d = cnt / i;
int dd = d - i;
if (abs(dd - diff) <= k) {
flag = 1;
break;
}
}
if (!flag) break;
ans++;
}
cout << ans << endl;
}
return 0;
}
'알고리즘 문제해결 > BOJ' 카테고리의 다른 글
BOJ 25402 트리와 쿼리 (0) | 2022.08.31 |
---|---|
BOJ 23090 난민 (0) | 2022.08.30 |
BOJ 24914 Split the SSHS (0) | 2022.08.29 |
BOJ 2647 검은점과 하얀점 (0) | 2022.08.14 |
BOJ 15961 회전 초밥 (0) | 2022.08.12 |