[백준] 2485번 : 가로수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2485번: 가로수

 

1. 문제 설명

2. 풀이과정

해당 문제는 새로 심어야 하는 가로수의 개수를 구하는 문제이다.

이미 심어져 있는 가로수를 보고 모든 가로수의 간격이 동일해지도록 가로수를 더 심어야 한다.

모든 가로수의 간격이 동일해지려면 이미 심어져 있는 가로수 간격들의 최대공약수를 구하여 그 수만큼 간격을 맞춰 새 가로수를 심으면 된다.

최대공약수는 gcd() 함수를 활용하여 구할 수 있고, 간격을 최대공약수로 나눈 몫에 1을 뺀 개수만큼 해당 간격에 새로 가로수를 심어야 한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 최대공약수를 구하는 gcd() 함수를 사용하기 위해 gcd 함수를 불러온다. from math import gcd
3. 이미 심어져 있는 가로수의 개수를 입력받는다. n = int(sys.stdin.readline())
4. 가로수의 위치를 저장할 리스트를 생성하고 num = list()
5. 가로수의 개수만큼 반복하며 for _ in range(n)
6. 위치를 입력받아 리스트에 추가한다. num.append(int(sys.stdin.readline()))
7. 가로수 간의 간격을 저장할 리스트를 생성하고 li = list()
8. 두 번째 가로수부터 마지막 가로수까지 반복하며 for i in range(1, n)
9. 바로 앞 가로수와의 간격을 리스트에 추가한다. li.append(num[i] - num[i - 1])
10. 가로수 간격들의 최대공약수를 저장할 변수를 생성하고 간격 하나를 저장한다. g = li[0]
11. 다음 간격부터 끝까지 반복하며 for i in range(1, len(li))
12. 현재 최대공약수와 해당 간격의 최대공약수를 구하여 저장한다. g = gcd(g, li[i])
13. 최종 새로 심어야 하는 가로수의 개수를 저장할 변수를 생성하고 초기화한다. result = 0
14. 간격을 하나씩 불러오며 for i in li
15. 간격을 최대공약수로 나눈 몫에 1을 뺀 값만큼 해당 간격에 가로수를 심는다. result += i // g - 1
16. 새로 심어야 하는 가로수의 개수를 출력한다. print(result)

반응형

3. 소스코드

import sys
from math import gcd

n = int(sys.stdin.readline())

num = list()
for _ in range(n):
    num.append(int(sys.stdin.readline()))
    
li = list()
for i in range(1, n):
    li.append(num[i] - num[i - 1])
    
g = li[0]
for i in range(1, len(li)):
    g = gcd(g, li[i])

result = 0
for i in li:
    result += i // g - 1

print(result)