20. Python(가로수)

[toc]

가로수

문제

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

---

제출

코드(시간 초과)

import sys

input = sys.stdin.readline

n = int(input())
n_lst = sorted([int(input()) for _ in range(n)])

rst_1 = 0
rst_2 = 0
current = 1
for num in n_lst:
    while current < num:
        if current % 2 != 0:
            rst_1 += 1
        else:
            rst_2 += 1
        current += 1
    current = num + 1

print(rst_1 if n_lst[-1] % 2 != 0 else rst_2)

# 입력
4
1
3
7
13

# 출력
3

---

인사이트

• 리스트 요소들의 간격을 보니 홀, 짝으로 나눠진 것을 보고 가장 큰 요소를 max로 설정 후 반복문으로 없는 수의 개수를 더하여 결과를 출력하려 했음
• 시간 초과로 다른 방법을 생각해 봄

---

코드(정답)

import sys
from math import gcd
from functools import reduce

input = sys.stdin.readline

n = int(input())
n_lst = [int(input()) for _ in range(n)]

distances = [n_lst[i] - n_lst[i - 1] for i in range(1, n)]

gcd_val = reduce(gcd, distances) # reduce(집계함수, 데이터) --> 데이터를 함수에 넣어 나온 값을 출력함 내장 함수를 사용할 때 도움이 됨

trees = sum((distance // gcd_val) - 1 for distance in distances) ## 양 끝에 배치된 가로수를 제외하기 위해 -1을 해줌

print(trees)

풀이

최대공약수(gcd) 활용

distances = [n_lst[i] - n_lst[i - 1] for i in range(1, n)]
gcd_val = reduce(gcd, distances)

• distances 리스트에 각 요소간 간격을 순서대로 계산함
• gcd_val 값에 reduce(gcd, distances) 값을 입력함
  • reduce(집계함수, 데이터) : 데이터를 집계함수에 넣어 나온 값을 출력
  • 즉, 각 요소간 간격의 최대공약수를 구함

trees = sum((distance // gcd_val) - 1 for distance in distances) ## 양 끝에 배치된 가로수를 제외하기 위해 -1을 해줌

• trees에 요소간 간격을 간격들의 최대공약수로 나눈 값(최소공배수 = 최소로 들어가야 할 가로수 개수)을 더하여 결과를 출력
• (distance // gcd_val) - 1의 -1은 양 끝의 가로수가 1개씩 있기 때문에 추가로 필요한 가로수의 개수를 구하기 위해 -1을 해주는 것

---