[java] 문제 042 (백준 1934)

문제

최소공배수

 

교재 풀이

import java.util.*;
public class P1934_최소공배수 {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    for (int i = 0; i < t; i++) {
      int a = sc.nextInt();
      int b = sc.nextInt();
      int result = a * b / gcd(a, b);
      System.out.println(result);
    }
  }
  public static int gcd(int a, int b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }
}

 

내 풀이) 24.6.21에 풀다가 gcd return 어떻게 할지 고민하다 정답 보고 미완성

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

public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int t=Integer.parseInt(br.readLine());
		
		for(int i=0;i<t;i++){
		    StringTokenizer st=new StringTokenizer(br.readLine());
		    int a=Integer.parseInt(st.nextToken());
		    int b=Integer.parseInt(st.nextToken());
		    System.out.println(a*b/gcd(a,b));
		}
		
	}
	
	public static int gcd(int a, int b){
	    if(b==0)
	        return a;
        gcd(b,a%b);
	}
}

확실히 retrun 을 어떻게 둬야 하나 
    내가 아는 바는 b가 0일 때 a를 반환하는 건데 
    gcd를 계속 콜해서 어느 순간 반환했어. 그럼 끝이잖아. 


//첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)
//T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
//T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
//
//접근법
//    최소공배수는 A*B/최대공약수임
//    최대공약수는 유클리드 호제법으로 구해주고 끝 
//    유클리드는 
//        gcd (a,b)
//            if b==0 
//                return a 
//            gcd(b,a%b)
//슈도코드
//    t를 입력받음 
//    for t만큼 반복해서 
//        a 받고 
//        b 받고 
//        print(a*b/gcd(a,b))
//    
//    gcd 구현 
//        인수론 a,b를 받고 리턴값은 int형이고 
//        if b==0 
//            return a 
//        gcd(b,a%b)

 

설명

• 재귀 호출 흐름
  1. 첫 번째 호출: gcd(6, 10)
     • a = 6, b = 10
     • b가 0이 아니므로, gcd(10, 6 % 10)을 호출합니다.
     • 6 % 10 = 6이므로, gcd(10, 6)을 호출합니다.
  2. 두 번째 호출: gcd(10, 6)
     • a = 10, b = 6
     • b가 0이 아니므로, gcd(6, 10 % 6)을 호출합니다.
     • 10 % 6 = 4이므로, gcd(6, 4)을 호출합니다.
  3. 세 번째 호출: gcd(6, 4)
     • a = 6, b = 4
     • b가 0이 아니므로, gcd(4, 6 % 4)을 호출합니다.
     • 6 % 4 = 2이므로, gcd(4, 2)을 호출합니다.
  4. 네 번째 호출: gcd(4, 2)
     • a = 4, b = 2
     • b가 0이 아니므로, gcd(2, 4 % 2)을 호출합니다.
     • 4 % 2 = 0이므로, gcd(2, 0)을 호출합니다.
  5. 다섯 번째 호출: gcd(2, 0)
     • a = 2, b = 0
     • b가 0이므로, a를 반환합니다.
     • 2를 반환합니다.
• 반환 흐름
  1. 다섯 번째 호출: gcd(2, 0)이 2를 반환합니다.
  2. 네 번째 호출: gcd(4, 2)은 gcd(2, 0)의 반환 값인 2를 반환합니다.
  3. 세 번째 호출: gcd(6, 4)은 gcd(4, 2)의 반환 값인 2를 반환합니다.
  4. 두 번째 호출: gcd(10, 6)은 gcd(6, 4)의 반환 값인 2를 반환합니다.
  5. 첫 번째 호출: gcd(6, 10)은 gcd(10, 6)의 반환 값인 2를 반환합니다.