글 읽기 - (java) 혹시 반례를 알수 있을까요?

angrynow 3년 전 0

이 문제를 유클리드 호제법으로 최대공약수를 구하면 풀린다는 건 알았습니다

근데 최대공약수를 다른 방법으로 구해봤는데 틀렸습니다가 나오네요

웬만한 반례를 다 넣어본거 같은데 그건 다 맞다고 나왔어요

혹시 어느 부분이 잘못됐는지 알려주시거나 반례를 알려주시면 감사하겠습니다

//백준 2609 최대공약수와 최소공배수
import java.io.*;
import java.util.*;

public class Main {
	public static ArrayList<Integer> firstList = new ArrayList<>();
	public static ArrayList<Integer> secondList = new ArrayList<>();
	public static ArrayList<Integer> commonDivisor = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder answer = new StringBuilder();
		
		int firstNumber = Integer.parseInt(st.nextToken());
		int secondNumber = Integer.parseInt(st.nextToken());
		//약수 찾기
		makeDivisor(firstNumber, firstList);
		makeDivisor(secondNumber, secondList);
		
		Collections.sort(firstList);
		Collections.sort(secondList);
		
		//공약수 찾기
		for(Integer firstN : firstList) {
			for(Integer secondN : secondList) {
				if(firstN == secondN) commonDivisor.add(firstN);
				else if(firstN < secondN) break;
			}
		}
		
		//최대 공약수 
		answer.append(commonDivisor.get((commonDivisor.size()-1))).append('\n');
		//최소 공배수
		int gcd = commonDivisor.get((commonDivisor.size()-1));
		int lcm = firstNumber * secondNumber / gcd;
		
		answer.append(lcm).append('\n');
		
		System.out.print(answer);
		
		br.close();
	}
	
	//약수 찾기
	public static void makeDivisor(int n, ArrayList<Integer> list) {
		for(int i = 1; i < (int)Math.sqrt(n) + 1 ; i++) {
			if(n % i == 0) {
				list.add(i);
			}
		}
		
		int size = list.size();
		
		for(int i = 0; i < size; i++) {
			list.add(n / list.get(i));
		}
	}

}

nahwasa 3년 전 0

반례입니다.

10000 10000

angrynow 3년 전 0

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(java) 혹시 반례를 알수 있을까요?

angrynow 3년 전 0

nahwasa 3년 전 0

angrynow 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말