호제법이라는 말이 두 수를 서로 나눠보면서 원하는 수를 얻어간다는 뜻이다.
유클리드 호제법은 최대공약수(gcd)를 구하는 알고리즘으로
두 수 a,b(a>=b) 일 때
gcd(a,b) { return b?gcd(b,a%b):a ; } 로 구현할 수 있다.
최대공약수 얘기를 한 겸 최소공배수(lcm)도 같이 얘기해야겠다.
최소공배수는 두 수 a, b 가 모두 가지는 배수의 최소값을 말한다.
최대공약수와 최소공배수의 관계에 따라 다음과 같이 구현할 수 있다.
lcm(a,b) { return a*b/gcd(a,b); }
두 수의 곱을 최대공약수로 나눈 값이 최소공배수 이다.
| 기본 기하 공식 (0) | 2020.02.28 |
|---|---|
| 볼록껍질 선분 처리하기 (0) | 2020.02.28 |
| 세그먼트 트리 정리 (0) | 2020.02.05 |
| 선분 교차 판별하기 (0) | 2020.02.02 |
| 삼분 탐색(Ternary search) (0) | 2020.01.16 |
BOJ : https://www.acmicpc.net/problem/1026
github : https://github.com/junho0956/Algorithm/blob/master/1026/1026/%EC%86%8C%EC%8A%A4.cpp
문제의 조건에 A와 B 배열의 값은 음이아닌 정수라고 하였다.
그러므로 두 배열의 각 인자들의 곱에 대한 합이 최소가 되기 위해서는
큰수는 작은수, 작은수는 큰수와 곱해주면 된다.
배열하나는 오름차순, 나머지 하나는 내림차순으로 정렬 후 곱해주면 된다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <algorithm>
using namespace std;
int A[51], B[51];
bool cmp(int& a, int& b) {
return a > b;
}
int main() {
int N; cin >> N;
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = 0; i < N; i++) cin >> B[i];
sort(A, A + N, cmp);
sort(B, B + N);
int ans = 0;
for (int i = 0; i < N; i++) ans += (A[i] * B[i]);
cout << ans;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
| BOJ 1043번 거짓말 (0) | 2020.03.13 |
|---|---|
| BOJ 1074번 Z (0) | 2020.03.05 |
| BOJ 2240번 자두나무 (0) | 2020.02.26 |
| BOJ 1504번 특정한 최단 경로 (0) | 2020.02.24 |
| BOJ 1238 파티 (0) | 2020.02.23 |
algospot : https://algospot.com/judge/problem/read/PASS486
** 시간제한 5000ms, 메모리제한 128MB **
이 문제를 푸는데에는 3가지 방법이 있습니다.
첫번째 방법
모든 수를 각각 약수를 다 구한다.
임의의 수 N 이 있을 때 1부터 sqrt(N)까지의 모든 수를 N에 mod 해보는 방법입니다.
이에 대해 각 수 당 시간복잡도는 sqrt(N)이 필요하고,
첫번째 방법을 이용해서 구현을 해보지는 않았는데 수의 범위가 최대 1000만이니
1000만*sqrt(N) 은 주어진 시간이 5초라서.. 사실 통과할것 같기는 합니다.
하지만 보통 이렇게 큰 시간을 허용해주지 않으니 다음 방법을 확인해보겠습니다.
두번째 방법
소수 알고리즘인 에라토스테네스의 체를 이용해서
각 수의 최소약수를 미리 구해놓으면 소인수분해를 빠르게 할 수 있고,
소인수분해를 이용해서 약수의 갯수를 빠르게 알 수 있습니다.
저는 이 방법을 통해서 800ms 로 해결했습니다.
종만북을 통해서 에라토스테네스의 체로 소인수분해를 할 수 있는 방법을 처음알았는데
감탄하고 갑니다..
세번째 방법은 완전히 소인수분해 하지 않고도 약수의 수를 셀 수 있는 방법인데,
두번째 방법보다 더욱 빠르다고 합니다.
아직 이해를 못해서 좀더 공부하고 차후 수정하겠습니다.
아래는 두번째 방법으로
에라토스테네스의체 -> 소인수분해 -> 약수의 갯수 찾는 순서로 구현되어 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
const int MAXNUM = 1e7 + 1;
int minFactor[MAXNUM];
int numFactor[MAXNUM];
void Factor() {
for (int i = 0; i < MAXNUM; i++) minFactor[i] = i;
for (int i = 2; i <= sqrt(MAXNUM); i++) {
if (minFactor[i] == i) {
for (int k = i * i; k < MAXNUM; k += i) {
if (minFactor[k] == k) minFactor[k] = i;
}
}
}
for (int i = 2; i < MAXNUM; i++) {
int n = i;
int ans = 1;
int cnt = 0;
int num = minFactor[i];
while (n > 1) {
if (minFactor[n] == num) cnt++;
else {
ans *= (cnt + 1);
cnt = 1;
num = minFactor[n];
}
n /= minFactor[n];
}
ans *= (cnt + 1);
numFactor[i] = ans;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
Factor();
int T; cin >> T;
while (T--) {
int n, lo, hi;
cin >> n >> lo >> hi;
int answer = 0;
for (int i = lo; i <= hi; i++) {
if (numFactor[i] == n) answer++;
}
cout << answer << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
| algospot FOSSIL (0) | 2020.02.26 |
|---|---|
| algospot RATIO (0) | 2020.02.25 |
| algospot LOAN (0) | 2020.02.24 |
| algospot ROOTS (0) | 2020.02.24 |
| algospot FESTIVAL (0) | 2019.10.27 |
BOJ : https://www.acmicpc.net/problem/2240
처음에는 solve(1번 나무,,) , solve(2번 나무..) 로 둘중에서 큰값을 선택하는 식으로 풀었는데
계속 WA가 뜨길래 어떤 문제점이 있는건지 도통 알수가없어서 포기했다.
몇일뒤에 다시 풀려고 문제를 천천히 읽어봤는데
자두는 1번나무 아래에 위치해 있다는 글을 읽었다..
그래서 solve(1번나무)만 구하니 AC를 받게 되었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int T, W;
int fall[1001];
int dp[3][1002][32];
int solve(int tree, int falling, int moving) {
if (falling < 0 || moving < 0) return 0;
int& res = dp[tree][falling][moving];
if (res != -1) return res;
res = 0;
if (tree == fall[falling]) res++;
res += max(solve(tree, falling - 1, moving), solve(tree == 1 ? 2 : 1, falling - 1, moving - 1));
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> T >> W;
for (int i = 0; i < T; i++) {
cin >> fall[i];
}
memset(dp, -1, sizeof(dp));
cout << solve(1, T, W);
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
| BOJ 1074번 Z (0) | 2020.03.05 |
|---|---|
| BOJ 1026번 보물 (0) | 2020.02.28 |
| BOJ 1504번 특정한 최단 경로 (0) | 2020.02.24 |
| BOJ 1238 파티 (0) | 2020.02.23 |
| BOJ 1916번 최소비용 구하기 (0) | 2020.02.23 |