2609번 문제 : 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수 (acmicpc.net)

2609번: 최대공약수와 최소공배수

package algorithm;

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

public class Main{
	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());
		
		int num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());
		int min = 0;
		int maxv = 0;
		int minv = 0;
		if(num1>num2) {
			min = num2;
		}
		else {
			min = num1;
		}
		for(int i=min;i>1;i--) {
			if(num1%i == 0 && num2%i ==0) {
				maxv = i;
				minv = i*(num1/i) * (num2/i);
				break;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(maxv+"\n"+minv);
		System.out.println(sb);
    }
}

이번에도 간단하게 해결했지만 틀렸대 !

아 9967 9973 같은 수가 들어왔을 때 최대공약수는 1인데 내가 for문 조건을 >로 해놔서 1은 구하질 않음 그래서  >=로 수정했다

 

맞음 ~~

package algorithm;

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

public class Main{
	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());
		
		int num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());
		int min = 0;
		int maxv = 0;
		int minv = 0;
		if(num1>num2) {
			min = num2;
		}
		else {
			min = num1;
		}
		for(int i=min;i>=1;i--) {
			if(num1%i == 0 && num2%i ==0) {
				maxv = i;
				minv = i*(num1/i) * (num2/i);
				break;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(maxv+"\n"+minv);
		System.out.println(sb);
    }
}

근데 이렇게 푸는게 아닌것 같다.

 

유클리드 호제법으로 풀어야한다구 한당... 공부해서 다시 시도해봐야겠다.

 

3/31

유클리드의 호제법으로 풀었다.

package algorithm;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
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());
		
		int num1 = Integer.parseInt(st.nextToken());
		int num2 = Integer.parseInt(st.nextToken());
		int min = 0;
		int max = 0;
		int GCF=0;
		if(num1>num2) {
			max = num1;
			min = num2;
		}
		else {
			max = num2;
			min = num1;
		}
		while(GCF ==0) { //최대공약수
			int R = max %min;
			if(R == 0)
				GCF = min;
			else { //나머지가 있으면
				max = min;
				min = R;
			}
		}	
		//최소공배수 LCM
		int LCM = num1*num2/GCF;
		System.out.println(GCF+"\n"+LCM);
    }
}