백준 2609번
https://www.acmicpc.net/problem/2609
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
2개의 숫자를 입력받아 num1
과 num2
의 두 변수에 저장해서 두 변수에서 최대공약수와 최소공배수를 찾으면 된다.
먼저 최대공약수 부터 보자면,
처음에 둘중에 작은 수를 선택해서 min
변수에 저장한다.
어차피 똑같이 나누어 져야하니까 작은 수를 기준으로 하나씩 줄여가면서 num1
과 num2
의 나머지가 0인 값을 찾으면 된다.
다음은 최소공배수이다.
최소 공배수를 찾을 때까지 무한 반복을 하게 두고
첫번째 공배수를 찾게되면 바로 break를 통해 반복을 중단한다.
첫번째 나오는 공배수가 최소공배수가 된다.
num1
과 num2
둘 중 하나를 선택하여 common_multiple
의 변수에 저장하고,
2부터 1씩 늘려가며 곱해서 다른 하나의 값과 나머지가 0이 되는 첫번째 값이 최소공배수가 된다.
이상하게 오늘 문제는 쉬었다.
왜 점점 쉬워지는 것 같지 기분탓인가?
문제를 많이 풀어서 어려운 문제에 빨리 도달하자.
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++; } } }
Don’t stop keep going