[백준 17087번 C++] 숨바꼭질 6

17087번: 숨바꼭질 6 (acmicpc.net)

17087번: 숨바꼭질 6

---

동생들의 위치를 vector a에 넣어두고, 

수빈과의 위치 차이를 vector dif에 넣었다.

따라서 vector dif에는 수빈이 동생을 찾으러 걸어야하는 걸음 수만이 저장되므로

vector dif에 저장된 수들의 최대 공약수를 찾으면 D의 최댓값을 구할 수 있다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(){
    int n, s, m;
    vector<int> a;
    vector<int> dif;
    
    cin >> n >> s;
    
    for(int i=0; i<n; i++){
        cin >> m;
        a.push_back(m);
    }
    
    //수빈이의 위치와 동생들의 위치의 차이값을 dif라는 벡터에 저장
    for(int i=0; i<a.size(); i++){
        if(a[i] < s) dif.push_back(s-a[i]);
        else dif.push_back(a[i]-s);
    }

    for(int i=0; i<dif.size(); i++){
        cout << dif[i] << " ";
    }
    
    return 0;
}

 

[C++]최대공약수 구하기(3가지 방법, 유클리드 호제법) (tistory.com)

[C++]최대공약수 구하기(3가지 방법, 유클리드 호제법)

동생의 수가 1명부터 시작하니까 

동생의 수가 1일 때는, d=dif[0]

동생의 수가 2일 때는, d=gcd(dif[0], dif[1])

동생의 수가 3 이상일 때는, for문에 d=gcd(d, dif[i]) 를 통해서 dif vector 안에 모든 수의 최대공약수를 d로 갱신한다

 

최종적으로 구해진 d를 출력했다

 

그렇게 만들어진 코드는

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b)
{ 
	if (a % b == 0) 
    	return b;
	else 
    	return gcd(b, a % b);
}


int main(){
    int n, s, m;
    vector<int> a;
    vector<int> dif;
    
    cin >> n >> s;
    
    for(int i=0; i<n; i++){
        cin >> m;
        a.push_back(m);
    }
    
    //수빈이의 위치와 동생들의 위치의 차이값을 dif라는 벡터에 저장
    for(int i=0; i<a.size(); i++){
        if(a[i] < s) dif.push_back(s-a[i]);
        else dif.push_back(a[i]-s);
    }
    
    int d; 
    if(n == 1) d=dif[0];
    else if (n == 2){
        d = gcd(dif[0], dif[1]);
    }
    else {
        d = gcd(dif[0], dif[1]);
        for(int i=2; i<n; i++){
            d = gcd(d, dif[i]);
        }
    }
    
    cout << d << "\n";
    
    return 0;
}