[Java] 백준 2609번 [최대공약수와 최소공배수] 자바

: ) YOUNG·2022년 1월 19일
2

알고리즘

목록 보기
40/411
post-thumbnail

백준 2609번
https://www.acmicpc.net/problem/2609


문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.


입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.


생각하기

2개의 숫자를 입력받아 num1num2의 두 변수에 저장해서 두 변수에서 최대공약수와 최소공배수를 찾으면 된다.

먼저 최대공약수 부터 보자면,
처음에 둘중에 작은 수를 선택해서 min변수에 저장한다.

어차피 똑같이 나누어 져야하니까 작은 수를 기준으로 하나씩 줄여가면서 num1num2의 나머지가 0인 값을 찾으면 된다.

다음은 최소공배수이다.
최소 공배수를 찾을 때까지 무한 반복을 하게 두고
첫번째 공배수를 찾게되면 바로 break를 통해 반복을 중단한다.

첫번째 나오는 공배수가 최소공배수가 된다.

num1num2둘 중 하나를 선택하여 common_multiple의 변수에 저장하고,
2부터 1씩 늘려가며 곱해서 다른 하나의 값과 나머지가 0이 되는 첫번째 값이 최소공배수가 된다.

TMI

이상하게 오늘 문제는 쉬었다.
왜 점점 쉬워지는 것 같지 기분탓인가?
문제를 많이 풀어서 어려운 문제에 빨리 도달하자.


코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		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 = Math.min(num1, num2);
		int common_divisor;

		// 최대 공약수
		for(common_divisor = min; common_divisor>=1; common_divisor--) {
			if(num1 % common_divisor == 0 && num2 % common_divisor == 0) {
				System.out.println(common_divisor);
				break;
			}
		}
	
		int i=2;
		int common_multiple = num1;

		// 최소 공배수
		for(;;) {			
			if(common_multiple % num2 == 0) {
				System.out.println(common_multiple);
				break;
			}
			common_multiple = num1 * i;
			i++;
		}

	}
}

1개의 댓글

comment-user-thumbnail
2022년 1월 21일

Don’t stop keep going

답글 달기