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

링크

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

난이도(solved.ac 참고)

실버2

풀이

input값 만큼의 1의 개수로 이뤄진 두 수의 최대공약수를 구하는 문제이다. 그냥 result에 '1'의 개수만큼 넣어서 구하면 메모리 초과가 뜬다. 그럴만도 한게 예제 입력 중에 500000000000000000이라는 매우 큰 수가 있기 때문.

 

저걸 다 구할 필요가 없다. 몇 자리 수인지만 알면 된다. 왜냐면 어차피 어떤 수든 간에 1로 바꿔준 수들이기 때문.. 일반적인 두 수의 최대 공약수를 구한 다음 그 갯수만큼 1로 바꿔주면 된다.