[BOJ] 2485. 가로수(Python)

www.acmicpc.net/problem/2485

2485번: 가로수

• gcd(Greatest Common Devisor) 최대공약수 구하는 함수 이용해서 148ms로 시간 단축 => 통과

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline
from math import gcd

n = int(input())
trees = []
gaps = []
for i in range(n):
    trees.append(int(input()))
    if i > 0:
        gaps.append(trees[i] - trees[i-1])

# 최대공약수 구하는 gcd 함수 이용
max_gap = gcd(gaps[0], gaps[1])
for i in range(1, n-1):
    max_gap = gcd(max_gap, gaps[i])     # 최대공약수 갱신

# 두 나무 사이 가장 긴 거리를 간격으로 나눈 몫 + 1이 전체 나무 수.
# 놓을 수 있는 전체 나무 수 - 주어진 나무 수 n을 빼주면 심어야하는 나무 수!
print((trees[-1]-trees[0]) // max_gap + 1 - n)

---

사실 이 전에 시도했던 O(N^2)의 효율성 꽝으로 풀었던 코드(이 코드도 통과 받긴 했다ㅋㅋ)

파이써닉하게 쓰라고 주어진 함수는 편하게 쓰라고 있는거다.. 적극 이용하자 gcd(최대공약수)!!

---

 

# 시간 1400ms의 효율성 꽝 코드..

n = int(input())
trees = []
gaps = []
for i in range(n):
    trees.append(int(input()))
    if i > 0:
        gaps.append(trees[i] - trees[i-1])
        
max_gap = 1
for k in range(2, min(gaps)+1):
    flag = True
    for gap in gaps:
        if gap % k:
            flag = False
            break
    if flag:
        max_gap = max(max_gap, k)

print((trees[-1] - trees[0]) // max_gap + 1 - n)

---

* 고찰 : 메서드는 이용하라고 있는거다. 괜히 안 쓰다가 엄청난 시간 폭격을 맞게 될 수 있다.. 푸는 데 30분 정도 소요.