JArchive 프로그래밍 일기

문제

숨바꼭질6 백준 17087번

리뷰

수빈이의 위치와 1명 이상의 동생들의 위치가 주어진다.

수빈이가 어떤 간격 D로 움직여야 동생들을 전부 만날 수 있냐는 문제다.

수빈이의 위치와 동생들의 위치를 빼서 '거리'를 구한 배열을 만든다.

배열을 전부 순회하면서 '최대공약수'를 구한다.

int gcd(int a, int b){ //  유클리드 호제법으로 구하는 a, b의 최대공약수 
    if(b == 0) return a;
    else return gcd(b, a%b);
}  

동생이 1명이 올수도 있고, 2명일 수도 있으니까 동생 숫자를 유의해야 한다.

맞은 코드

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

int N, S, D; // 동생 수, 수빈 위치  
int A[100001]; // 동생들 위치  

int gcd(int a, int b){ // 최대공약수 

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

int main(void){

    scanf("%d %d", &N, &S);

    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]); // 동생의 위치 입력받음  
        A[i] = abs(A[i] - S); // 수빈의 위치와 동생의 위치의 '차이'로 갱신   
    }

    if(N == 1){ // 동생 수 N 1명  

        D = A[0];
    }else if(N == 2){ //동생 2명  

        D = gcd(A[0], A[1]); 
    }else{ 

        D = gcd(A[0], A[1]);

        for(int i = 2; i < N; i++){
            D = gcd(D, A[i]);
        }    
    }

    printf("%d", D);

    return 0;
}