백준 2485 - 가로수

문제

---

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

 

 

 

풀이

---

# 백준/실버4/가로수

# 유클리드 호제법
# a,b가 있을 때, a를 b로 나눈값을 b, 기존의 b를 a로 바꾸면서
# b가 0이 될때까지 반복한다.

def gcd(a,b):
    while b > 0:
        a,b = b,a % b
    
    return a

n = int(input())

data = []

# 입력값
for _ in range(n):
    data.append(int(input()))

# 가로수 사이의 격차를 저장
diff = []

for i in range(1,len(data)):
    diff.append(data[i] - data[i-1])

# 격차 간의 최대공약수를 구한다
g = diff[0]
for j in range(1,len(diff)):
    g = gcd(g, diff[j])

# 가로수 개수를 세는 변수
cnt = 0

# 가로수 값은 격차 // 전체 격차의 최대공약수 - 1

# if 3 9 13
# diff = 6,4
# gcd = 2
# 3 (5,7) 9 (11) 13 이므로
# 6 // 3 -1 = 2 때문에 3과 9사이에 2개의 가로수가 세워진다.
for k in diff:
    cnt += k // g - 1

print(cnt)

 

그냥 구현했더니 시간초과

 

개인적으로는 두 지점에서 이해가 잘 안갔다

 

1. 왜 최대공약수를 사용하며, 모든 간격간에 적용하는가?

 

2. 왜 cnt += k // g - 1에서 -1을 적용할까?

 

 

내가 생각한 답은

1. 문제는 최소한의 개수로 가로수를 세워야한다.

   모든 가로수를 일정 간격으로 세우기 위해서는 최대공약수만큼의 차이만 가능하다.  

   ex. 간격이 1,7,3이면 최대공약수인 1로 설정해야 함

   1과7의 최대 공약수는 1, 이 최대공약수와 3을 비교하면 1이 나온다. 그냥 (1*2)*3, 1*(2*3)의 결과가 같은 것과 같은 원리     라고 이해함.

 

2. 나는 가로수를 한 지점에 채우는 것으로 생각함 근데 -1을 안해주는 것은 그냥 그 면적을 채울때는 맞는데 가로수 하나가

세워질때는 -1을 적용해야함. 

 

약간 이런 느낌으로 간격 2로 앞뒤 2개의 간격을 채우니까 -1을 적용하여 하나의 가로수가 필요한 것