[백준/JAVA] 1850번: 최대공약수

ㅇ🔺 문제

1850번: 최대공약수

 

🔺 코드

- 틀림

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        
        long result = gcd(a, b);
        long num = 0;
        
        for(long i = 0 ; i < result ; i++) {
            num += Math.pow(10, i);
        }
        bw.write(num +"\n");
        bw.flush();
        bw.close();        
    }
 
    
    // 최대공약수 계산
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
}

정답은 천만 자리를 넘지 않는다고 하는데,

이 수가 너무 커서 long long에 담길 수 없기 때문이라 함.

 

글 읽기 - 알맞게 한 것 같으나 틀렸다고 합니다

 

 

- 정답

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        
        long result = gcd(a, b);
        long num = 0;
        
        while(result > 0) {
            bw.write("1");
            result--;
        }
        bw.flush();
        bw.close();        
    }
 
    // 최대공약수 계산
    public static long gcd(long a, long b) {
        if(b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
}

✅ 해결 아이디어
✔ 유클리드 호제법
- 1 출력 : 최대공약수만큼 출력

 

💥 유의사항

⇨ 위에도 썼듯, 숫자가 너무 커서 Math.pow(10, i)로는 숫자를 담을 수 없다 함.

⇨ 시간 초과가 발생할 수 있으므로 BufferedWriter를 써줘야 함.

 

 

---

💬 느낀 점

재밌구나..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ Math.pow(10, i)가 틀린 이유...

글 읽기 - 알맞게 한 것 같으나 틀렸다고 합니다