[알고리즘 PS] 백준 1850번 최대 공약수 자바 문제풀이

문제

해당 포스팅은 백준의 1850번 최대 공약수 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

이번 문제는 최대 공약수를 구하는 단순한 문제에서 조금 변형을 한 형태이다.

이 변형 덕분에 문제의 정답률이 30%라고 생각하는데, 잘 따라온다면 그리 어렵지 않은 변형이다.

해결법

문제에서는 다음 두 개의 입력을 준다.

1. A : 첫 번째 수의 자리수
2. B : 두 번째 수의 자리수

이렇게 A와 B를 받게 된다면 우리는 1을 A번과 B번 각각 이어 붙혀 하나의 수를 만들 수가 있다.

 

만약 A가 3이고 B가 6이라면

A = 111
B = 111_111

이와 같이 구성된다.

 

여기서 문제는 이 A와 B가 만든 수 끼리 최대공약수 GCD를 구하라는 문제이다.

 

단 조건이 A와 B는 2^62제곱으로 대략 10경의 자리수가 올 수 있다.

 

오해하면 문제 틀린다.

 

10경은 1000조가 10개 있는데, 이 10경의 자리수는 16승이다.

 

A가 16이고 B가 16이면

A = 1111111111111111
B = 1111111111111111

인 셈이다.

 

이게 총 10경의 자리수라면 우린 절대로 일반 자료형으로 해결하지 못한다.

 

다른 방법을 찾아야 한다.

접근법

이 문제에서 주어지는 A와 B 자리수를 생각해보자.

• A = 3 이고 B = 6 이면 111이라는 수가 최대공약수가 된다.
• A = 5 이고 B = 10 이면 11111가 최대공약수가 된다.
• A = 5 이고 B = 15 이면 11111가 최대공약수가 된다.

A = 111;
B = 111_111;
answer = 111;

A = 11111;
B = 11111_11111;
answer = 11111;

A = 11111;
B = 11111_11111_11111;
answer = 11111;

규칙이 보이나?

 

좀 더 직관적으로 바꿔보겠다.

• A = 3 이고 B = 6 이면 111이라는 수가 즉 1의 3자리 최대공약수가 된다.
• A = 5 이고 B = 10 이면 11111가 즉 1의 5자리 최대공약수가 된다.
• A = 5 이고 B = 15 이면 11111가 즉 1의 5자리 최대공약수가 된다.

이렇게 된다면 사실상 A와 B에 최대공약수를 구하고 결과 수만큼 1에 1자리만큼 추가해주면 된다.

주의 하자

주의하자 a와 b는 2^63 제곱의 수다.

이 말은 java의 int형으로 처리할 수 없다는 뜻이다.

long 형은 2^64 제곱까지 표현할 수 있으므로 long형이 적절해 보인다.

정답 코드

public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String[] ab = br.readLine().split(" ");

    long a = Long.parseLong(ab[0]);
    long b = Long.parseLong(ab[1]);

    if(a < b) {
      long temp = a;
      a = b;
      b = temp;
    }

    while(b > 0) {
      long temp = b;
      b = a % b;
      a = temp;
    }

    while(a-- > 0) {
      bw.write("1");
    }

    bw.flush();
    bw.close();
  }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.