[백준/Python] - 2485번 가로수

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

 

📜제출코드 

#최대 공약수를 활용해서 푸는 문제

import sys

input = sys.stdin.readline

N = int(input())

N_list = [int(input())]

intervals = []

# 유클리드 호제법

def gcd(a,b):

    while b >0:

        a, b = b, a % b

    return a

for _ in range(1,N):

    N_list.append(int(input()))

    intervals.append(N_list[_] - N_list[_-1])

# 최대 공약수로 구하는 간격의 초기값을 입력해주고

max_num = intervals[0]

for i in range(1,len(intervals)):

# 최대 공약수를 이용해서 추가할 수 있는 나무를 최소화 한다.

# --> 나무의 간격을 최대화 해야된다

    max_num = gcd(max_num,intervals[i])

total_len = N_list[-1] - N_list[0]

total_interval = total_len // max_num

need_interval = total_interval - len(intervals)

print(need_interval)

 

📜풀이

수학에 관해서 너무 약해서 챗지피티의 도움을 받아서 문제를 해결했다...

 

문제에서 거리가 가까운 순서대로 주어진다고 했다.

그리고 간격을 최대로 해서 최소한의 가로수를 심으려고 한다. 라고 되어있어서 

최대공약수를 이용해서 문제를 풀어야했다.

 

1. 가로수 사이의 길이 구하기

for _ in range(1,N):

    N_list.append(int(input()))

    intervals.append(N_list[_] - N_list[_-1])

 가로수 사이의 길이를 구해준다.

 

2. 가로수 사이의 길이 최대 공약수 구하기

for i in range(1,len(intervals)):

# 최대 공약수를 이용해서 추가할 수 있는 나무를 최소화 한다.

# --> 나무의 간격을 최대화 해야된다

    max_num = gcd(max_num,intervals[i])

가로수 사이의 간격을 동일하게 최대로 하기위해서 각 간격에 대해 최대공약수를 구해준다.

 

3. 총 간격 수 구하기

total_len = N_list[-1] - N_list[0]

total_interval = total_len // max_num

마지막 가로등과 첫번째 가로등을 빼줘서 전체 거리를 구한다.

전체 거리에서 일정 간격(max_num)값으로 나누면 총 간격수가 나타나는데

 

4. 필요한 간격 수 구하기

need_interval = total_interval - len(intervals)

현재 있는 간격 개수를 빼주면 

필요한 간격수가 나오는 것이다.