2981번: 검문
문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는
www.acmicpc.net
문제를 보고 뭔가 최대 공약수의 약수들을 출력하면 될 거 같다는 솔루션을 얻는데까지는 오래 걸리지 않았다.
하지만 문제는 M으로 나눴을 때 나머지가 같은 M을 출력하는 것이었기에, 입력받은 숫자 중 가장 작은 숫자를 M으로 하고 그 수를 1씩 감소하면서 나눴을 때 나머지가 같은 M을 벡터에 저장하고, 나머지가 0이 되면 그 때의 M이 최대공약수이므로 최대공약수 M의 약수들을 출력해주는 식으로 구현하려했다.
하지만 999999999, 999999998, 999999997 이런식으로 숫자가 주어지게 되면 1씩 감소해가지고는 시간초과가 날 것이 분명했기 때문에 잘못된 접근이라 생각하고 다른 사람들의 풀이를 참고하였다.
최대공약수를 구하는 유클리드호제법에 대하여 알게 되었고, 3개 이상 숫자들의 최대공약수를 구하는법도 알게되었다.
|
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 <vector>
#include <algorithm>
using namespace std;
vector<int> v, result;
int GCD(int a, int b) // 최대공약수 구하기
{
if (a % b == 0)
return b;
return GCD(b, a%b);
}
int main(void)
{
int testcase;
cin >> testcase;
while (testcase--)
{
int number;
cin >> number;
v.push_back(number);
}
sort(v.begin(), v.end());
int diff = v[1] - v[0];
for (vector<int>::size_type i = 2; i < v.size(); i++)
diff = GCD(diff, v[i] - v[i - 1]);
for (int i = 2; i*i <= diff; i++)
{
if (diff%i == 0)
{
result.push_back(i);
result.push_back(diff / i);
}
}
result.push_back(diff);
sort(result.begin(), result.end());
vector<int>::iterator iter_end = unique(result.begin(), result.end()); // 중복된 원소를 뒤로 넘김
for (vector<int>::iterator iter = result.begin(); iter != iter_end; iter++)
cout << *iter << ' ';
cout << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 24day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 1405번: 미친 로봇 (0) | 2020.05.03 |
|---|---|
| 백준 1213번: 팰린드롬 만들기 (0) | 2020.04.30 |
| 백준 1062번: 가르침 (0) | 2020.04.29 |
| 백준 6679번: 싱기한 네자리 숫자 (0) | 2020.04.28 |
| 백준 1074번: 게임 (0) | 2020.04.28 |