백준 2485
- 백준 2485 : 가로수 (https://www.acmicpc.net/problem/2485)
보아하니 sort되서 위치값이 가로수의 위치로 들어온다.
각 가로수 사이의 거리를 구하고 저장한다.
이들의 최대공약수를 구한다.(가로수 사이의 거리들)
거리의 최솟값에서 1까지 가면서 해당 수를 공약수로 갖는지 확인하고, 공약수면 break한다.
입력값을 받을 때, 첫째 위치와 마지막위치를 따로 저장한다.
그림 그려 보니
마지막 위치에서 첫째 위치를 빼서 총 거리를 구하고,
그것을 얻은 최대공약수(gap)으로 나눈다.
단, 이것은 맨 첫 지점은 무조건 박고 시작한다를 기준으로 하기 때문에 (n-1)
따라서
총 거리/ gap - (n-1)을 하면 총 몇개의 가로수가 들어가야 할지 나온다.
https://github.com/JangJuMan/2019-winter-PS/blob/master/21_2485.cpp
끗
ㅇㅁㅇ?!