[BOJ_1850] 최대공약수

문제 링크: https://www.acmicpc.net/problem/1850

1850번: 최대공약수

내 풀이:

Review:

 구현의 아이디어까지 어렵지 않은 문제이지만 코드를 제출했을 때 시간 초과를 3번이나 받았다... 그래서 어떻게 하면 시간을 단축할 수 있을지 고민해봤다. 먼저 최대공약수를 구하는 함수를 내장 함수 gcd()로 바꿔보기도 하고, 다음으로 두 수의 대소 비교를 통해 튜플의 값을 서로 교환하는 과정도 추가하고, 결론적으로는 구한 최대공약수를 int()를 통해 정수로 바꿔주는 과정을 뺐더니 문제를 해결할 수 있었다.

 

Idea:

 문제의 조건에 두 수의 일의 개수가 주어진다. 이때 해당 수를 문자열 1에 곱하고, 타입을 변환하여 최대공약수를 구한다면 분명히 시간 초과가 날 것이다. 문제의 조건을 보면 입력되는 수가 2^63으로 아주 큰 수이기 때문이다. 그래서 주어진 두 수를 가지고 바로 최대공약수를 구한 뒤 해당 수를 문자열 1의 곱한 결과 문제에서 주어진 결괏값을 구할 수 있었다.