-
[Python] BOJ 2485 : 가로수코딩테스트/백준 2024. 9. 23. 08:30
요구사항
- 임의의 간격으로 심어져 있는 가로수 사이에 추가로 가로수들을 심어 연속된 가로수들 간의 차이가 일정하게 한다.
- 새로 심어야 하는 가로수의 최소수를 구해라.
설계
- 임의 설치된 가로수의 개수를 받는다.
- 임의 설치될 가로수의 위치를 받는다. (양의 정수)
- 연속되어 있는 가로수들 중 차이가 가장 적은 수를 구한다.
- 첫 번째 가로수부터 다 더한다.
위 설계의 예외
# 임의로 설치된 가로수 2 4 6 11
재설계
- 설계의 1~2번 동일
- 연속된 가로수들의 최대공약수를 구한다. 3과 5 의 최대공약수는 1 따라서 위 설계의 예외 시에도 가능하다.
- 새롭게 심을 가로수의 최소수는 아래 공식을 따른다.
- (마지막 가로수 - 첫 번째 가로수) / GCD - (이미 심어진 가로수 - 1)
- 결과를 출력한다.
정답 답안 예시
import sys, math input = lambda: sys.stdin.readline().rstrip() N = int(input()) trees = [int(input()) for _ in range(N)] distances = [trees[i] - trees[i-1] for i in range(1,N)] gcd = distances[0] for d in distances[1:]: gcd = math.gcd(gcd, d) new_trees = (trees[-1] - trees[0]) // gcd - (N-1) print(new_trees)
'코딩테스트 > 백준' 카테고리의 다른 글
[Python] BOJ 1929 : 소수 구하기 (0) 2024.09.23 [Python] BOJ 4134 : 다음 소수 (0) 2024.09.23 [Python] BOJ 10816 : 숫자 카드 2 (0) 2024.09.22 [Python] BOJ 7785 : 회사에 있는 사람 (2) 2024.09.22 [Python] BOJ 10815 : 숫자 카드 [9.26 이후 다시 볼 게시물] (0) 2024.09.22