[BAEKJOON]1850 최대공약수

문제 요약

• 알고리즘 분류: 유클리드 호제법
• 난이도: Silver1
• 문제내용:
  • A, B 1의 개수가 주어지면 A, B의 최대 공약수를 구해라
• 사이트 주소: https://www.acmicpc.net/problem/1850

1850번: 최대공약수

 

문제 풀이

 이번 문제는 유클리드 호제법이다. 유클리드 호제법에 대한 설명은 여기에서 확인해보면된다. 하지만 1의개수가 최대 억이상 갈수 있어서 일반적인 유클리 호제법으로 풀다가는 메로리 초과와 시간 초과 나올수 있기 때문에 다른 방법으로 풀어야한다.

 문제 접근 방법

  위 2의 63승까지 범위이면 자리수만 해도 터무니없느 숫자이다. 그래서 각 1의 개수를 최대공약수를 구하지 말고 A B의 수를 최대 공약수를 구해서 1을 최대 공약수 만큼 곱하면 답이 나온다.

Code

Python

import math

A, B = map(int, input().split())
print("1" * math.gcd(A, B))

Java

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long A = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < gcd(A, B); i++) {
			sb.append("1");
		}
		System.out.println(sb);
		
	}
	
	public static long gcd(long x, long y) {
		if(y == 0) {
			return x;
		}
		return gcd(y, x % y);
	}	

}