백준_2824 최대공약수(자바) / 구현 & 수학

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_2824 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BigInteger a = new BigInteger("1");
		BigInteger b = new BigInteger("1");
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			a = a.multiply(new BigInteger(st.nextToken()));
		}
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			b = b.multiply(new BigInteger(st.nextToken()));
		}
		String tmp=a.gcd(b).toString();
		StringBuilder sb = new StringBuilder();
		if(tmp.length()>9) {
			for (int i = 0; i < 9; i++) {
				sb.append(tmp.charAt(tmp.length()-9+i));
			}
			System.out.println(sb);
		}else {
			System.out.println(tmp);
		}
	}
}

 

※ 내 생각

이 문제는 구현 및 수학 문제입니다.

처음에는 각각의 수의 약수를 배열에 담고 위 아래 겹치는 것을 계산하는 방식으로 진행하려고 했습니다.
약수를 구하려면 만약 10억인 경우 10억 * (N+M) 의 for문을 돌아야 해서 시간 부족이 발생할듯 하여 방법을 바꿨습니다.

Long의 범위로 해결이 안됬고. 다른 것을 찾던 중 블록체인에서 사용하던 BigInteger 사용했고,
사칙 연산 및 심지어 gcd 구할 필요도 없었네요... 다 들어 있습니다
BigInteger에 대해서 알면 쉽게 풀 수 있었던 문제
BigInteger에서 계산 하려면 메서드를 이용해서 해결을 해야 하는데 찾던 중에 메서드 목록에 gcd가..... 👍
gcd 구하는 문제가 있으면 BigInteger를 사용하면 편하게 풀 수 있겠네요