[코드업] 디지털 도어 락 (C++)

코딩테스트/코드업

[코드업] 디지털 도어 락 (C++)

Deff_a 2024. 5. 5. 00:39

디지털 도어 락

XX사에서 만든 디지털 도어락은 내부적으로 보안키 값을 가지고 있고, 이 값은 1,000이하의 자연수로 이루어져 있다. 각 카드키들은 ID값을 가지고 있는데, 이 값이 도어락의 내부 보안키 값의 약

codeup.kr

문제

이 문재는 입력된 3개의 수의 최대 공약수를 구하는 문제이다.

풀이

유클리드 호제법을 이용하여 최대 공약수를 구했다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란

ko.wikipedia.org

#include <iostream>
// https://codeup.kr/problem.php?id=2650
using namespace std;

// 유클리드 호제법
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int key1, key2, key3;

    // 3개의 내부 보안키 값을 입력 받는다.
    cin >> key1 >> key2 >> key3;

    // 첫 번째와 두 번째 수의 최대공약수를 구한다.
    int gcd1 = gcd(key1, key2);

    // 위에서 구한 최대공약수와 세 번째 수의 최대공약수를 구한다.
    int masterKey = gcd(gcd1, key3);

    // 계산된 값(최대공약수)을 출력한다.
    cout << masterKey << endl;

    return 0;
}