백준 2485번 python 풀이

 

 

딱 문제를 봤을때 든 생각은

a, b, c, ... , z 까지의 나무가 이미 심어져있다고 가정했을때

각 나무사이의 간격을 저장해놓고, 간격들의 최대공약수를 구하여 그중에서도 최소값을 이용해 간격에 사용한다

그리고 처음과 끝 사이에 심어줄 나무의 개수 - 이미 존재하는 나무 개수 를 구하면 된다고 생각했다

맨 처음에 짰던 코드는 위의 말한 과정을 여러 개의 반복문을 이용하여 구현했다

 

<초기코드>

import sys, math

n = int(input())
d = {}
s = set()
check = 1000000000
r = 0

for i in range(n):
  d[i] = int(sys.stdin.readline())

for i in range(1, n):
  s.add(d[i] - d[i-1])

s = list(s)

for i in range(1, len(s)):
  g = math.gcd(s[i-1], s[i])
  if check > g:
    check = g

i = d[0]
count = 1
ic = d[count]
while i < d[n-1]:
  if ic != i:
    r += 1
  else:
    count += 1
    ic = d[count]
  i += check

print(r-1)

 

그런데 답은 맞았지만 자꾸 시간초과 오류가 뜨는 것...

시간초과에 관해 서칭하다가 마지막 카운트부분에서 소스를 확 줄일 수 있는 방법을 발견했다

 

참고코드:https://rileydev.tistory.com/45

다른 부분말고 맨 마지막의 카운트 부분의 식만 참고하였다

 

이번에는 시간초과 오류는 나지 않고 틀렸다고 떴다...

반례를 게시판에서 찾다가 유레카!!

심어야 할 나무가 0개일 때를 고려하지 못했던 것이다

 

그래서 추가한 부분은 집합의 길이가 1이라면 간격의 길이는 항상 동일하다는 의미이기 때문에

check = s[0]를 추가해주었다

 

결과는 성공~~!!

 

<최종코드>

import sys, math

n = int(input())
d = {}
s = set()
check = 1000000000
r = 0

for i in range(n):
  d[i] = int(sys.stdin.readline())

for i in range(1, n):
  s.add(d[i] - d[i-1])

s = list(s)

if len(s) == 1:
  check = s[0]
else:
  for i in range(1, len(s)):
    g = math.gcd(s[i-1], s[i])
    if check > g:
      check = g

print((d[n-1] - d[0]) // check-(n-1))