| 작성자 | 이재영 |
| 일 시 | 2024. 11. 26 (화) 18:00 ~ 21:00 |
| 장 소 | 미래관 429호 자율주행스튜디오 |
| 참가자 명단 | 임혜진, 장원준, 이재영, 성창민, 김명원 |
| 사 진 |  |
2981번: 검문
트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간
www.acmicpc.net
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b){ //유클리드 호제법을 이용한 최대공약수 구하기 알고리즘
if(a<b){ //a에 더 큰 수가 놓일 수 있도록 swap
int tmp = a;
a = b; b = tmp;
}
int r = a % b;
if(r != 0){
return gcd(b,r); //gcd(a,b)==gcd(b,r)
}else{
return b;
}
}
void divisor(int a) { // 약수 구하기
if (a <= 0) {
return;
}
for (int i = 1; i <= a / 2; i++) {
if (a % i == 0) {
if(i!=1) cout << i << " "; // 약수를 구하는대로 출력
}
}
cout << a << endl; //마지막으로 자기 자신을 출력
}
int main(){
int N; cin>>N;
int arr[N];
for(int i=0;i<N;i++){
int tmp; cin>>tmp;
arr[i]=tmp;
} // 수를 입력받아 배열에 차례로 저장
sort(arr,arr+N); //오름차순으로 정렬
int diff[N-1];
for(int i=0;i<N;i++){
diff[i] = arr[i+1]-arr[i]; //이웃한 수의 차를 또다른 배열에 저장
}
int ans = diff[0]; //ans의 초기값
for(int i=0;i<N-2;i++){
ans = gcd(ans,diff[i+1]);//ans와 diff의 최대공약수를 구하고 이를 ans에 저장함
}
divisor(ans); //ans의 약수를 구함
cout<<endl;
}어떤 수 M으로 나누었을 때, 나머지가 모두 같게 되는 어떤 수 M은? 이걸 생각하는데 좀 시간이 걸렸다.
예제를 보면서 갈피를 잡았다. 백준에서 주어진 예제2를 보면
입력 5 5 17 23 14 83
출력 3 이다.
나머지가 같다는 것은 나눈 수(M)의 배수에 같은 수가 더해진다는 것이다.
예제 2에서는 출력이 3이니 M이 3임을 아는 상태에서 생각해보자.
5 = 3 * 1 + 2
17 = 3 * 5 + 2
23 = 3 * 7 + 2
14 = 3 * 4 + 2
83 = 3 * 27 + 2
이처럼 몇 배수인지는 다 다르지만 더해지는 수(나머지)는 2로 같다.
따라서 이를 이용할 수 있다.
17에서 5를 빼면
17 - 5 = (3*5+2) - (3*1+2) = 3*(5-1)
나머지가 상쇄되어 사라지기 때문에 딱 나누어 떨어지게 된다.
따라서 나머지 없이 M으로 나누어 떨어지는 수, 9가 구해진다.
9 같이 M으로 나누어 떨어지는 수를 여러 개 구해서 그 수들의 최대공약수를 구하면 되겠다고 생각했다.
따라서 입력받은 수를 오름차순으로 정렬해서 그 차이를 diff라는 배열에 저장했다. 그리고 diff 안에 있는 수들에 대해서 최대공약수 연산을 해주었다.
하지만 여기서 하나 더 처리해주어야 할 것이 있었는데, 최대공약수가 아니라 최대공약수의 약수를 출력해야한다는 점이었다. 따라서 약수를 구하는 연산이 필요했다. 단순히 a/2까지 반복문을 돌면서 a가 나누어지는지 다 나누어보는 방식을 이용했다.
C++ 갑자기 하고 싶어서 해봤는데, 오랜만에 하니까 C++ 참 어렵다고 느꼈습니다. 이번이 마지막 모각코지만 알고리즘 공부는 계속해야 겠다고 느꼈습니다.