https://www.acmicpc.net/problem/1850
시간 2초, 메모리 256MB
input :
- A와 B를 이루는 1의 개수
output :
- A와 B의 최대공약수를 출력
처음에 그냥 예제들을 gcd 메소드에 넣고 출력을 해봤다.
3 4 -> 1
3 6 -> 3
500000000000000000 500000000000000002 -> 2
그래서 저 숫자만큼 1을 출력하면 되나? 하다가 그냥 잘못 구한 거겠지 하고
1을 입력 받은 만큼 정수로 바꿔서 실제로 구하려고 하니 당연히 시간 초과가 발생했고.
다른 사람들의 풀이를 보니 위에 한 생각이 맞았다. ㄴㅇㄱ
일단 gcd계산 하는 방법을 다시 해보자.
def gcd(n, m):
if n < m:
n, m = m, n
while n % m:
n, m = m, n % m
return n작은 숫자로 큰 숫자를 나눈 나머지가 존재한다면 계속 반복하는 형식
를 만들거나 아니면 math.gcd를 이용하자.
import sys
from math import gcd
n, m = map(int, sys.stdin.readline().split())
cnt = gcd(n, m)
for i in range(cnt):
print(1, end="")
