[Python] 백준 1850번 - 최대공약수

https://www.acmicpc.net/problem/1850

1850번: 최대공약수

 

혼자 힘으로 풀었는가? X

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

 

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

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

입력

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

출력

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

 

---

문제 이름부터 대놓고 최대공약수였다.

 

하지만 난 최대공약수를 구하는 방법을 까먹었고 결국 검색을 해야만 했다.

 

2022.08.11 - [Algorithm/백준] - [Python] 백준 1934번 - 최소공배수 (최소공배수, 최대공약수, 유클리드호제법)

[Python] 백준 1934번 - 최소공배수 (최소공배수, 최대공약수, 유클리드호제법)

 

이전에도 정리해놓은 최대공약수, 최소공배수, 유클리드 호제법에 대한 정리글이다.

해당 문제도 간단하게 유클리드 호제법을 이용해서 풀 수 있었다.

 

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

def foo(x, y):
  r = x%y
  x = y
  y = r
  while r:
    r = x%y
    x = y
    y = r
  return x
print("1"*foo(a, b))

---

 

 

(오답)

 

처음엔 문제를 보고 이해가 안돼서 예제를 보고 패턴을 찾으려 했었다.

 

나랑 비슷한 사람도 있었다 심지어

 

3 4
1

3 6
3

500000000000000000 500000000000000002
11

위에서 패턴을 보니

 

큰 수 - 작은 수 * "1" 하면 답이 나오는 것이다.

 

import sys
input = sys.stdin.readline

a, b = map(int, input().split())
c = abs(a-b)
s = "1"*c
print(s)

당연히 해당 문제는 틀렸고

 

https://www.acmicpc.net/board/view/97053

글 읽기 - 메모리 초과 질문합니다

 

당당하게 오답이었다.