C++ 코딩테스트 강좌, Ax + By = C

본 강좌에서는 C++ 언어를 이용하여 Ax + By = C 형태의 방정식을 푸는 방법에 대해 알아보겠습니다.
이 문제는 코딩테스트에서 자주 접할 수 있는 내용으로, 수학적 이해와 알고리즘 설계를 필요로 합니다.

문제 정의

주어진 정수 A, B, C가 있을 때, 방정식 Ax + By = C를 만족하는 정수 x와 y의 모든 조합을 구하는 문제입니다.
주의할 점은 x와 y가 정수여야 한다는 것입니다. 예를 들어 A=2, B=3, C=6일 때,
(x, y) = (0, 2), (3, 0), (1, 1)와 같은 정수 쌍이 있습니다.

문제 해결을 위한 기초 수학 개념

이 문제를 해결하기 위해서는 디오판틴 방정식(Diophantine Equation) 개념을 알아야 합니다.
디오판틴 방정식은 정수 계수를 가진 다항 방정식에서 정수 해를 찾는 문제입니다.
Ax + By = C 형태의 방정식이 일관된 해를 가지려면, gcd(A, B)가 C의 약수여야 합니다.

알고리즘 설계

1. 먼저 A, B, C의 GCD를 계산합니다.
2. GCD가 C의 약수인지 확인합니다.
3. GCD가 C의 약수이면, x와 y의 가능한 조합을 찾기 시작합니다.
4. 정수 해를 찾기 위해 x의 값은 0부터 시작하여 B로 나눈 나머지를 검토합니다.
5. 각 x에 대해 y를 계산하여 정수 해를 찾습니다.

C++ 코드 구현

아래는 위 알고리즘을 C++로 구현한 예시 코드입니다:

# include <iostream>
# include <vector>
# include <numeric> // for std::gcd
using namespace std;

// Ax + By = C 방정식을 만족하는 (x, y)의 모든 조합을 구하는 함수
void findIntegerSolutions(int A, int B, int C) {
    int gcd_ab = gcd(A, B);

    // GCD가 C의 약수인지 확인
    if (C % gcd_ab != 0) {
        cout << "해가 존재하지 않습니다." << endl;
        return;
    }

    // A, B, C를 GCD로 나누어 정규화
    A /= gcd_ab;
    B /= gcd_ab;
    C /= gcd_ab;

    // x의 가능한 범위를 설정
    for (int x = -100; x <= 100; ++x) {
        // y를 계산
        if ((C - A * x) % B == 0) {
            int y = (C - A * x) / B;
            cout << "(x, y) = (" << x << ", " << y << ")" << endl;
        }
    }
}

int main() {
    int A, B, C;
    cout << "A, B, C 값을 입력하세요: ";
    cin >> A >> B >> C;

    findIntegerSolutions(A, B, C);
    return 0;
}

코드 설명

– 입력으로 A, B, C를 받고 findIntegerSolutions 함수를 호출합니다.
– A, B의 GCD를 계산하여 return하고, 이를 통해 C가 GCD의 약수인지 검사합니다.
– GCD로 모든 수를 나눈 후, x의 값을 -100에서 100까지 변화시키며 y를 계산합니다.
– 방정식이 성립하는 경우 x, y 쌍을 출력합니다.

결과 보기

이제 코드 실행 결과를 확인해보겠습니다. 예를 들어 A=2, B=3, C=6인 경우 다음과 같은 결과를 얻을 수 있습니다:

A, B, C 값을 입력하세요: 2 3 6
(x, y) = (0, 2)
(x, y) = (3, 0)
(x, y) = (1, 1)

결론

이번 강좌에서는 Ax + By = C 형태의 방정식을 C++로 해결하는 방법을 살펴보았습니다.
이 문제를 통해 디오판틴 방정식의 기초 이론과, 이를 해결하기 위한 알고리즘 설계를 익히게 되었습니다.
이러한 문제는 코딩테스트에서 자주 출제되므로, 충분히 연습하셔서 자신만의 풀이 방법을 찾는 것이 중요합니다.