[BOJ/JAVA] 백준 1850 : 최대공약수 (자바)

문제 정보

  문제명   - 최대공약수
  난이도   - 실버 II
문제 번호 - 1850번

---

문제 링크

BOJ_S2_1850_최대공약수

1850번: 최대공약수

---

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.
예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

---

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

---

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

---

예제 입력/출력

예제 입력	예제 출력
3 4	1
3 6	111
500000000000000000 500000000000000002	11

---

알고리즘 분류

● 수학
● 정수론
● 유클리드 호제법

---

소스코드

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 수학, 정수론, 유클리드 호제법
 * https://www.acmicpc.net/problem/1850
 * 
 * 다짜고짜 1로 이루어진 숫자를 구하려고 하면 안된다.
 * 유클리드 호제법을 활용하면
 * 1111 = 111x10 + 1
 * 111 = 11x10 + 1
 * 11 = 1x10 + 1
 * 이런식으로 추론할 수 있다.
 */
public class BOJ_S2_1850_최대공약수 {
	public static long gcd(long a, long b) {
		if(a%b == 0)
			return b;
		return gcd(b, a%b);
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder str = new StringBuilder();
		// A의 길이만큼 1로 이루어진 a
		long A = Long.parseLong(st.nextToken());
		// B의 길이만큼 1로 이루어진 b
		long B = Long.parseLong(st.nextToken());
		// 유클리드 호제법을 활용해서 최대공약수를 구함
		for (long i = 0; i < gcd(Math.max(A, B), Math.min(A, B)); i++)
			str.append("1");
		
		System.out.println(str);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---