코딩 테스트 [정수론] - Ax + By = C

A, B, C가 주어졌을 때 Ax + By = C를 만족하면서 다음 조건을 만족하는 (x, y) 쌍을 찾으시오.

· x, y는 정수
· -1,000,000,000 ≤ x, y ≤ 1,000,000,000

(시간 제한 1초)

---

입력

1번째 줄에 정수 A, B, C가 주어진다.

출력

Ax + By = C를 만족하는 x, y를 공백으로 구분해 출력한다. 문제의 조건을 만족하는 (x, y)가 존재하지 않을 때는 -1을 출력한다.

· -1,000,000 ≤ A, B, C ≤ 1,000,000
· A, B ≠ 0

예제 입력
3 4 5	// A B C

예제 출력
-5 5

---

1단계 - 문제 분석하기

확장 유클리드 호제법을 그대로 구현하면 되는 문제이다.

2단계 - 손으로 풀어 보기

1 C의 값이 A와 B의 최대 공약수의 배수 형태인지 확인한다. 최대 공약수의 배수 형태라면 C의 값을 최대 공약수로 변경한다. 최대 공약수의 배수 형태가 아니라면 -1을 출력한 후 프로그램을 종료한다.

2 A와 B에 관해 나머지가 0이 나올 때까지 유클리드 호제법을 수행한다.

3 나머지가 0이 나오면 x = 1, y = 0으로 설정한 후 과정 2에서 구한 몫들을 식(x = y', y = x' - y' * 몫)에 대입하면서 역순으로 계산한다.

4 최종으로 계산된 x, y값에 C를 x와 y의 최대 공약수로 나눈 값을 각각 곱해 방정식의 해를 구한다.

5 / gcd(a, b) = 5, | x = -1 x 5 = -5 | y = 1 x 5 = 5
⇒ 정답은 (-5, 5)

3단계 - sudo코드 작성하기

a(1번째 수) b(2번째 수) c(3번째 수)
최대 공약수 = gcd(a, b)

if(c가 최대 공약수의 배수가 아니라면)
	-1 출력 후 프로그램 종료
else
{
	나머지(b)가 0이 될 때까지 재귀 함수를 호출하는 유클리드 호제법 함수 호출하기
    결괏값에 c/최대 공약수의 값을 곱한 후 해당 값 출력
}

Excute(a, b)
{
	if(b == 0)
    	return;
    
    Excute(b, a % b)
    
    x = y', y = x' - y' * 몫을 계산하는 역산 로직 구현
}

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

4단계 - 코드 구현하기

import java.util.Scanner;

public class Q45 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c =sc.nextInt();

        long gcd = gcd(a,b);

        if(c%gcd != 0)
            System.out.println("01");
        else{
            int K = (int) c / (int)gcd(a,b);
            long[] ret = Excute(a, b);
            System.out.println(ret[0] * K + " " + ret[1] * K);
        }
    }

    private static long[] Excute(long a, long b){
        long[] ret = new long[2];

        if(b == 0){
            ret[0] = 1;
            ret[1] = 0;
            return ret;
        }

        long q = a / b;
        long[]v = Excute(b, a % b);
        ret[0] = v[1];
        ret[1] = v[0] - v[1] * q;
        return ret;
    }

    private static long gcd(long a, long b){
        if(b == 0)
            return a;
        else
            return gcd(b, a  % b);
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편