[Do It! 코딩테스트 자바편(김종관)] 문제 045(백준 21568번)

난이도

확장 유클리드 호제법을 그대로 구현하는 문제다. 이 이론은 이해못해서 고민하다가 교재 이론 설명하고 코드 풀이하고 번갈아 보면서 이해하는 것을 중점으로 했다. 따라서 확장 유클리드 호제법 알고리즘은 이런 거구나를 공부한 셈이다.

문제

Ax+By=C (백준: 21568번)

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MainTest {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    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);
    if (c % gcd != 0) {
      System.out.println(-1);
    } else {
      int mok = (int) (c / gcd);
      long[] ret = Excute(a, b);
      System.out.println(ret[0] * mok + " " + ret[1] * mok);
    }
  }

  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]; // 역으로 올라오면서 X Y값을 계산해주는 로직
    ret[1] = v[0] - v[1] * q;
    return ret;
  }

  private static long gcd(long a, long b) {
    while (b != 0) {
      long temp = a % b;
      a = b;
      b = temp;
    }
    return Math.abs(a);
  }
}