[백준] 3036. 링

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

<문제>

첫번째 원이 돌아갈 때 다른 원들은 몇 번을 도는지를 계산해 출력하는 문제다.

 

<풀이>

1. 일단 첫번째로 원이 회전하는 것은 원의 둘레에 따라 달라지고 원의 둘레를 구하는 식은 2ㅠr인데 2ㅠ는 약분되어 사라지므로 영향을 미치는 요소는 r만 남게 된다. 따라서 원의 반지름의 길이가 곧 얼마나 회전하는지를 결정하는 요소이므로 원의 반지름 길이의 비율을 출력하면 된다.

2. 출력할 비율을 기약분수 형태로 나타내려면 어떻게 해야 할 지 생각해보았다. 기약분수는 더 이상 공통된 수로 나눠지지 않는 수이므로 가장 큰 공통약수로 나눈면 더 이상 나눠지지 않을거라는 생각을 했고, 가장 큰 약수를 구하는 개념은 최대공약수이다.

3. 따라서 원들의 반지름을 첫번째 원과의 최대공약수로 나누면서 그 값을 저장해 출력하면 된다고 생각했다.

 

<코드1>

import math

n = int(input())
numList = list(map(int, input().split()))
answer = ""

for i in range(1, len(numList)):
    gcd = math.gcd(numList[0], numList[i])
    answer += f"{numList[0]/gcd:0.0f}/{numList[i]/gcd:0.0f}\n"
    
print(answer)

32952 kb

88 ms

 

<코드2>

from collections import deque
import math
from sys import stdin

n = int(input())
numList = list(map(int, input().split()))

for i in range(1, len(numList)):
    gcd = math.gcd(numList[0], numList[i])
    print(f"{numList[0]/gcd:0.0f}/{numList[i]/gcd:0.0f}")

33020 kb

88 ms

위의 코드는 정답 문자열을 저장하지 않고 바로 출력하면 메모리를 적게 사용할 수 있지 않을까? 하는 생각에 시도해 보았는데 차이는 없었고, 오히려 아주 약간 메모리가 증가하는 결과를 보였다.

이를 통해, 정답을 변수에 저장해서 한 번에 출력을 하던 바로바로 출력을 하던 결과에는 큰 차이가 없다는 것을 알 수 있었다.

 

<코드3>

def GCD(a,b): return GCD(b,a%b) if b else a

N = int(input())
li = list(map(int, input().split()))
result = ''
for i in range(1,len(li)):
    tmp = GCD(li[0],li[i])
    result += str(li[0]//tmp) + '/' + str(li[i]//tmp) +'\n'
print(result)

30840 kb

68 ms

이 코드와 내가 작성한 코드의 차이는 최대공약수(GCD)를 구하는 방식이다. 나는 math클래스의 gcd( )를 사용해서 구했는데 여기서는 직접 계산해 값을 반환했고, 여기서 속도의 차이가 난 것으로 보인다.

평소에는 gcd함수를 사용하는 것이 편하지만 익숙해지거나 속도를 조금이라도 더 빨리 내야 한다면 직접 계산하는 방식을 사용하는 것이 좋을 것 같다.