[백준 1850번] 최대공약수

 

www.acmicpc.net/problem/1850

1850번: 최대공약수

 

[문제]

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 

이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

 

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

 

<알고리즘 분류> 수학, 정수론, 유클리드 호제법

 

[input]

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.

[output]

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

 

---

 

 

---

 

[풀이 방법]

- Scanner 사용 시 시간 초과 발생

- BufferedReader+BufferedWriter 사용

1. A와 B를 한 줄로 입력받아 split 함수를 통해 구분하여 배열 ab에 저장

2. 각각 long 타입으로 변환하여 A와 B에 저장

3. 미리 정의한 gcd함수 활용하여 최대공약수 구하고, 그 수만큼 1 출력

 

---

 

실패 코드 - 시간 초과

 

성공 코드