[백준 - 21568] Ax + By = C .java

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

 

 

확장 유클리드 호제법

목적: 방정식의 해 구하기

 

예) ax +by = c

x,y가 정수해를 가지려면 c가 a와 b의 최대 공약수의 배수여야한다.

-> c % gcd(a,b) = 0

=> 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)이다.

 

 

문제 풀이

확장 유클리드 호제법을 이용하여 해를 구했다.

 

1. 입력받은 c = a, b의 최대 공약수의 배수 인지 확인 -> 배수가 아니면 -1, 배수면 c = 두 수의 최대 공약수로 변경
2. a,b를 가지고 나머지가 0일 때까지 유클리드 호제법을 수행
3. 나머지가 0이 나오면 역순으로 거슬러 올라가 몫을 이용해 x,y를 구한다(시작값 x=1,y=0)
4. 위에서 구한 x,y값 * k(c/gcd(a,b)를 곱하여 최종 답을 구한다

 

유클리드 호제법을 공부하고 바로 적용한 문제라 무슨 알고리즘을 써야할 지 분명하여 그나마 접근하기 쉬웠다.

하지만 직접 구현하는 것에서 역순으로 접근하는것이 어려웠다. 그래서 재귀적 호출의 위치를 고민했다.

여러 위치로 해본 결과 단순하게 재귀에서 빠져나오는 영역에서 실행하면 자연스럽게 역순이 되는 것을 알았다.

생각보다 간단했다......

 

 

 

import java.io.*;
import java.util.StringTokenizer;

public class p21568 {

    public static void main(String[] args) throws IOException {
        //효율적인 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //효율적인 출력 처리
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //띄어쓰기로 구분
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        long gcd = gcd(a, b);//a와 b의 최대공약수를 계산
        if(c % gcd != 0){//해가 없음
            System.out.println("-1");
        } else{//해가 있으면
            int k = (int) (c / gcd);//최초해는 k배
            long[] answer = Excute(a,b);//a와 b의 해를 구하기
            System.out.println(answer[0]*k +" "+answer[1]*k);
        }
    }

    //최소공약수 찾기
    public static long gcd(long p, long q) {
        if (q == 0) return p;
        else return gcd( q, p % q);
    }
    //해를 구하는 함수
    public static long[] Excute(int a, int b) {
        long[] list = new long[2];//0번째가 x,1번째가 y
        if(b ==0){//시작값: x=1,y=0
            list[0] = 1;
            list[1] = 0;
            return list;
        }
        long mok = a /b;//몫
        //재귀적으로 확장 유클리드 알고리즘을 호출 -> 빠져나오면 역순으로 계산됨
        long[] pre = Excute(b, a%b);
        //x와 y를 갱신
        list[0] = pre[1];
        list[1] = pre[0] - pre[1] * mok;
        return list;
    }


}