[백준] 1850 : 최대공약수 - JAVA

Benjamin·2023년 1월 19일

백준

BAEKJOON

목록 보기

42/71

문제분석

입력되는 수가 2^63보다 작은 자연수이면, 최대가 2^63 자리수인데.. 너무 큰 수라서 유클리드호제법으로도 가능할지 모르겠다.

입력받은수중 하나가 2^63일 경우, 유클리드 호제법을 정말 gcd(10^(2^63-1)+1 % B)로 해야할지.. 조금 막막해서 찾아봤다.

주어진 예제를 바탕으로 규칙을 찾을 수 있다.

입력받은 두 수(수의 길이를 나타냄)의 최대공약수 = A,B최대공약수의 길이

-> 막막하면 이렇게 예제를 통해 규칙을 찾을 수 있어야하나? 생각도 못한 접근이다.

슈도코드

A,B의 길이 입력받기
euclid(A,B);
1을 gcd의 자릿수만큼 출력 

euclid(A,B) {
	if(A<B) {
    	swap연산 수행
    }
    int result = A%B
    if(result == 0) gcd = B;
    else euclid(B,result);
}

Troubleshooting

public class gcd43 {
static long gcd;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long aLength = Integer.parseInt(st.nextToken());
		long bLength = Integer.parseInt(st.nextToken());
		euclid(aLength,bLength);
		for(long i=0; i<gcd; i++) {
			bw.write("1");
		}
		bw.flush();
		bw.close();
	}
	public static void euclid(long aLength,long bLength) {
		if(aLength<bLength) {
			long temp = aLength;
			aLength = bLength;
			bLength = temp;
	    }
	    long result = aLength%bLength;
	    if(result == 0) gcd = bLength;
	    else euclid(bLength,result);
	}
}

문제

원인

처음에 입력을 int타입으로 받았어서 에러가났다. long으로 변경하면서 입력타입 변환하는 메서드도 수정하는걸 놓쳤다.

해결

범위를 초과하기때문에 모든 입력과 result, gcd 등 변수의 타입을 long으로 변경했으므로, Integer.parseInt ->Long.parseLong 으로 수정

어려운건 아니었고, 숫자입력은 처음부터 보통 long으로 입력받도록 습관들이는게 좋다!!

제출코드

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

public class Main {
static long gcd;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long aLength = Long.parseLong(st.nextToken());
		long bLength = Long.parseLong(st.nextToken());
		euclid(aLength,bLength);
		for(long i=0; i<gcd; i++) {
			bw.write("1");
		}
		bw.flush();
		bw.close();
	}
	public static void euclid(long aLength,long bLength) {
		if(aLength<bLength) {
			long temp = aLength;
			aLength = bLength;
			bLength = temp;
	    }
	    long result = aLength%bLength;
	    if(result == 0) gcd = bLength;
	    else euclid(bLength,result);
	}
}