[백준] 1850 최대공약수 -Java

 

 

 

일반적인 접근방법으로 풀면 메모리 초과가 발생하거나 시간 초과가 발생한다. 새로운 방법을 생각해보자.

 

입력값으로 들어온 숫자들에 대해 111... 로 변환하지 않고 최대공약수를 구해 보면, 출력값은 111... 로 변환했을 때의 출력값과 어떠한 연관관계를 찾을 수 있다.

 

변환 전 숫자의 최대공약수만큼 1을 추가해서 출력해주면 된다.

 

 

Java

 

 

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

public class Main {


	public static void main(String[] args) throws IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		if(b>a){
			long temp = a;
			a = b;
			b = temp;
		}
			
		
		
		long gcd = gcd(a,b);

		for(int i=0; i<gcd; i++){
			sb.append("1");
		}
		System.out.println(sb);


	
	} 
	static long gcd(long a, long b){
		while(b != 0){
			long r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}