[BOJ/백준] 17087 숨바꼭질 6

● [문제번호 17087] 숨바꼭질 6

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

17087번: 숨바꼭질 6

 

● 알아야 할 것

: vector 자료구조와 메소드

: 유클리드 호제법

 

● 풀이 과정

: 처음에 문제에 대한 이해를 못했다.

한 번에 동생들을 찾는 최댓값 D?

예제 입력과 출력을 보면 거리 차이의 최솟값인거 같은데.. 하며

일단 문제 오류인가 싶어 최솟값을 찾았으나 결과는 '틀렸습니다' 로 계속 나왔다.

그래서 내가 문제 이해를 제대로 하지 못하고 있다고 느끼고 구글링을 하였다.

바로 이해하고 나니 생각이 짧았구나 하고 느꼈다.

 

: 문제에서 구하고자 하는 것은 (수빈이와 동생들의 거리 차)들의 최대공약수이었다.

각 거리의 차를 구하고 그 차이들의 최대공약수를 구하면 된다.

 

● 주의 할 것

: 최대공약수를 구하는 과정에서

기존에 구하던 단순한 방법 (두 수 중 작은 값부터 작아지면서 공약수를 구하는 방법)을 사용하면 '시간 초과'의 결과가 나온다. → O(N)

하지만 유클리드 호제법을 사용하면 나눗셈으로 더 빠르게 작아진다. → O(log N)

 

● 참고 할 것

: 유클리드 호제법 gcd( a , b ) = gcd( b , a % b )

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 동생의 위치를 저장할 vector A
// 동생과 수빈의 위치 차이를 저장할 vector S_A
vector<int> A, S_A;
int N, S;
int D;

// 최소공배수를 구하는 함수
// 유클리드 호제법 사용
// (순차적으로 확인하는 작업은 '시간초과' 결과를 가져옴)
int GCD(int a, int b)
{
    if(b == 0)
        return a;
    
    return GCD(b, a % b);
}

// 수빈이와 각 동생과의 거리 차이들을 저장하고
// 그 차이들의 최소공배수를 구한다
void check_gcd()
{
    // 수빈이와 각 동생과의 거리 차이 저장
    for(int a = 0; a < A.size(); a++)
        S_A[a] = abs(S - A[a]);
    
    // 유클리드 호제법 사용을 위한 정렬 (필수X)
    sort(S_A.begin(), S_A.end());
    
    // 각 차이들의 최소공배수를 구한다
    D = S_A[0];
    for(int a = 1; a < S_A.size(); a++)
        D = GCD(S_A[a], D);
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S;
    
    // 초기 vector 할당
    A.assign(N, 0);
    S_A.assign(N, 0);
    
    // 입력
    for(int n = 0; n < N; n++)
        cin >> A[n];
    
    // 최소공배수 구하기
    check_gcd();
    
    // 출력
    cout << D;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [301 - 수학 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	9613	GCD 합	https://pirateturtle.tistory.com/189
2	17087	숨바꼭질 6	https://pirateturtle.tistory.com/190
3	1373	2진수 8진수	https://pirateturtle.tistory.com/191
4	1212	8진수 2진수	https://pirateturtle.tistory.com/192
5	2089	-2진수	https://pirateturtle.tistory.com/193
6	17103	골드바흐 파티션	https://pirateturtle.tistory.com/194