{% embed url=“https://www.acmicpc.net/problem/2609” %}
Solution 1. 유클리드 호제법 + 재귀함수
•
14240 kb / 124 ms
•
풀이방법
◦
유클리드 호제법 + 재귀함수를 이용해서 풀었다.
package practice.algorithm.math;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Bj2609_1 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); if (a < b) { int temp = a; a = b; b = temp; } System.out.println(gcd(a, b)); System.out.println(lcm(a, b)); } private static int lcm(int a, int b) { return a * b / gcd(a, b); } private static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }}
Java
복사
Solution 2. 유클리드 호제법 + 반복문
•
14216 kb / 124 ms
•
위와 같은 알고리즘이지만, 표현방식을 재귀함수가 아닌, 반복문을 이용해보았다.
package practice.algorithm.math;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Bj2609_2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); if (a < b) { int temp = a; a = b; b = temp; } System.out.println(gcd(a, b)); System.out.println(lcm(a, b)); } private static int lcm(int a, int b) { return a * b / gcd(a, b); } private static int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }}a
Java
복사