[BOJ]17087번: 숨바꼭질 6(java, c++)

https://www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
 
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            int iSisNum = Integer.parseInt(st.nextToken());
            int iOrigin = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
 
            int[] arrAbsNums = new int[iSisNum];
            
            for (int i = 0; i < iSisNum; i++) {
                arrAbsNums[i] = Math.abs(iOrigin - Integer.parseInt(st.nextToken()));
            }
            
            int iGCD = Math.abs(arrAbsNums[0]);
            
            for (int i = 1; i < iSisNum; i++) {
                iGCD = GCD(iGCD, arrAbsNums[i]);
            }
            
            System.out.println(iGCD);
 
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
 
    public static int GCD(int A, int B) {
 
        if (B == 0) {
            return A;
        } else {
            return GCD(B, A % B);
        }
    }
}

 

c++ 소스

#include <iostream>
#include <vector>
 
using namespace std;
 
int GCD(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    return GCD(b, a % b);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, S;
    cin >> N >> S;
 
    // 동생과 수빈이의 위치 차이를 저장
    vector<int> sister_gap(N);
    for (int i = 0; i < N; i++)
    {
        cin >> sister_gap[i];
        sister_gap[i] = (S - sister_gap[i] > 0) ? S - sister_gap[i] : sister_gap[i] - S;
    }
 
    // 개별 차이값들의 최대공약수 계산
    int gcd = sister_gap[0];
    for (int i = 1; i < N; i++)
    {
        gcd = GCD(gcd, sister_gap[i]);
    }
 
    cout << gcd;
 
    return 0;
}

 

 

TIP

D씩 이동할 수 밖에 없으므로, |수빈 - 동생| 값들의 GCD를 구하는 문제

 

1. 절대값들을 먼저 모두 구하여 배열로 저장하고 난 후,

2. 배열 요소들의 GCD를 구하자