백준 2485 파이썬

백준 1735 - 분수 합

문제

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

2485번: 가로수

2485번

답안 코드 :

import sys
from math import gcd

# 이미 심어져 있는 가로수 수 
N = int(sys.stdin.readline())

# 첫 가로수 위치 
a = int(sys.stdin.readline())

# 가로수들 사이의 값을 저장할 배열
arr = []

# 가로수들 사이의 간격 저장 
for i in range(N-1):
    num = int(sys.stdin.readline())
    arr.append(num - a)
    a = num

# arr에 들어있는 모든 수들의 최대공약수 찾기
g = arr[0]
for j in range(1, len(arr)):
    g = gcd(g, arr[j])

# 둘 사이에 심을 가로수 개수: 간격 // 최대공약수 - 1
result = 0
for each in arr:
    result += each // g - 1
print(result)

백준 / 문제 / 단계별로 풀어보기 / 15단계 약수, 배수와 소수 2

생각 :

# 같은 간격으로 가로수 -> 각 간격들의 최대공약수
# 두 가로수 사이에 심을 가로수의 개수 = 간격 // 최대공약수 -1