백준 2485번 풀이

문제

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

2485번: 가로수

간격을 일정하게 심으려면 나무가 최소 몇 개 필요한가?

 

Reference

https://jyzinn.tistory.com/111

[Python] 백준 2485번 가로수

https://blockdmask.tistory.com/525

[python] 파이썬 최대공약수, 최소공배수 함수 (gcd, lcm)

 

풀이

일단 지금까지 풀었던 문제에는 다 유클리드 호제법이 들어가 있는데, 이번 문제는 그렇게 할 수가 없다. 왜냐하면 유클리드 호제법 함수는 숫자가 두개 들어가는데 풀다보면 나오는 나무 간격이 세개거든... 아니, 네개 다섯개도 될 수 있는데... 이게 왜 문제냐고? 간격이 세 개면 유클리드 호제법을 세 번 돌아야 하고, 네 개면 6번, 5개면 10번 돌아야 한다. n개면 nC2다. 이거 이거면 진지하게 메모리 초과는 둘째치고

이 소리 듣기 딱 좋습니다.

import sys
import math

K = int(sys.stdin.readline().strip())
tree_list = []

for i in range(K):
    tree_loc = int(sys.stdin.readline().strip())
    tree_list.append(tree_loc)

tree_list.sort()

항상 그렇듯 입력에서 고민할 필요는 없다. sort는 혹시 몰라서 해줬음…

 

tree_gap = []

for i in range(1, K):
    gap = tree_list[i] - tree_list[i-1]
    tree_gap.append(gap)

tree_gcd = math.gcd(*tree_gap)
# math.gcd는 숫자만 넣을 수 있기 때문에 리스트는 언패킹을 해 줘야 한다

위에서 내가 유클리드 호제법 함수는 두개밖에 안들어가서 나무 간격이 많아질때마다 저거 돌리는 횟수도 늘어난다고 했는데, math에 있는 gcd는 숫자? 다 들어오라고 전해라! 가 된다. 근데 대신에 리스트나 튜플은 언패킹(리스트 안에 있는걸 풀고 요소만 넣는거라고 보면 된다)을 해 줘야 구할 수 있기 때문에 앞에 애스터리스크가 붙은 것. 애스터리스크가 붙어있으면 언패킹하라는 얘기다.

 

아, 저거 안 틀리냐고? 다른 풀이에도 다 저거 쓴다.

 

tree_add = 0
for i in tree_gap:
    tree_add += (i // tree_gcd) - 1

print(tree_add)

tree_gap을 통해 tree_gcd를 구했으면 인제 걔가 나무 간격의 공차가 되는거다. 그러면 나무 사이사이 몇 개가 비는지를 추가할건데, 예시에 있는 1, 3, 7, 13을 예로 들면 tree_gap은 2, 4, 6이 된다. 그러면 공차가 2니까(간격들의 최대공약수가 2) 첫번째는 간격을 여기서 더 나누지 않아도 된다. 그리고 4의 경우 둘로 나누려면 가운데에 나무 하나를 심어야 하니까 1, 6은 나무 두 개를 심어야 하니까 2. 1 안 빼면 각각 1, 2, 3 나와서 틀려요.

 

import sys
import math

K = int(sys.stdin.readline().strip())
tree_list = []

for i in range(K):
    tree_loc = int(sys.stdin.readline().strip())
    tree_list.append(tree_loc)

tree_list.sort()

tree_gap = []

for i in range(1, K):
    gap = tree_list[i] - tree_list[i-1]
    tree_gap.append(gap)

tree_gcd = math.gcd(*tree_gap)
# math.gcd는 숫자만 넣을 수 있기 때문에 리스트는 언패킹을 해 줘야 한다

tree_add = 0
for i in tree_gap:
    tree_add += (i // tree_gcd) - 1

print(tree_add)

근데 그 가로수 설마 은행나무는 아니겠지...