수학 1 연습 해보자
-
- GCD 합 (low): 이중 for 문으로 묶어서 더하면 되는 간단한 문제였다.
9613번: GCD 합
문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 ��
www.acmicpc.net
|
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
|
#include <iostream>
using namespace std;
int gcd(int x, int y) {
while (y != 0) {
int r = x%y;
x = y;
y = r;
}
return x;
}
int main()
{
int t;
int tc[100];
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> tc[i];
long sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sum += gcd(tc[i], tc[j]);
}
}
cout << sum << '\n';
}
return 0;
}
|
cs |
=> 입력 가능한 범위를 보고, 애초에 커질 것 같으면 long이나 long long을 사용하자..
- 숨바꼭질 6 (low): 최대공약수를 사용하는 문제라는 것을 캐치하는 것이 중요한 문제였다.
17087번: 숨바꼭질 6
수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이�
www.acmicpc.net
|
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
|
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int gcd(int x, int y) {
while (y != 0) {
int r = x%y;
x = y;
y = r;
}
return x;
}
int main()
{
int n, s, a;
cin >> n >> s;
vector<int> v;
for (int i = 0; i < n; i++) {
cin >> a;
v.push_back(a);
}
if (v.size() == 1) {
cout << abs(v[0] - s);
}
else if (v.size() == 2) {
cout << gcd(abs(v[1] - s), abs(v[0] - s));
}
else {
long long temp, ans;
temp = gcd(abs(v[1] - s), abs(v[0] - s));
for (int i = 2; i < n; i++) {
ans = gcd(abs(v[i] - s), temp);
temp = ans;
}
cout << ans << '\n';
}
return 0;
}
|
cs |
=> 2개 이상의 최대공약수를 구하려면 gcd(gcd(a,b), c) 이런 식으로 감싸면 된다.
- 골드바흐 파티션(high): 중복 되지 않게 카운트 하는 것이 까다로워서 많이 헤맸다.
17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
|
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
|
#include <iostream>
#include <vector>
using namespace std;
bool check[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
vector<int>prime;
for (int i = 2; i <= 1000000; i++) {
if (check[i] == false) {
prime.push_back(i);
for (int j = i * 2; j <= 1000000; j += i) {
check[j] = true;
}
}
}
int t;
cin >> t;
while (t--) {
int n, cnt = 0;
cin >> n;
for (int i = 0; i < prime.size(); i++) {
if (n-prime[i] >= 2 && prime[i] <= n - prime[i]) {
if (check[n-prime[i]] == false) cnt++;
}
else {
break;
}
}
cout << cnt << '\n';
}
return 0;
}
|
cs |
- 15: 에라토스테네스의 체를 사용해서 입력 가능 범위 안의 소수를 모두 구한다.
- 31~35: 입력한 수에서 소수를 뺀 수가 2이상이어야 하고, 뺀 소수보다 같거나 커야 한다. 앞의 조건은 소수가 되기 위한 조건, 뒤의 조건은 앞뒤가 바뀐 쌍을 중복해서 카운트 하지 않기 위한 조건이다. 그 다음 골드바흐 성립 여부를 조사해서 카운트를 한다. 조건을 벗어나면 반복문을 나온다.
-
진법을 바꾸는 문제도 있었는데, 알고리즘적으로 크게 중요하지 않은 내용이란다.
사실상 컴퓨터가 다 해주는 일이니까 굳이 알고리즘으로 설계할 필요가 없어서 인 것 같다.
2진법에서 8진법으로, 8진법에서 2진법으로 어떤 식으로 변환이 되는지만 알아두면 충분한듯 하다.
수학1의 연습 문제는 다소 적었다. 여기서 마무리!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제1) (0) | 2020.07.09 |
|---|---|
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 (0) | 2020.07.08 |
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (연습) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (큐, 덱) (0) | 2020.07.06 |
