백준 2485 - 가로수 (파이썬)
글 작성자: pental

https://www.acmicpc.net/problem/2485
풀이
가로수들이 일정하지 않은 간격으로 심어져 있다. 이 간격을 모두 같게 만들기 위해 새로운 나무들을 더 심어야한다.
- 현재 심어진 가로수의 좌표가 주어진다.
- 추가로 심어야 하는 나무의 수를 구하는 문제이다.
풀이과정은 다음과 같다.
- 각 인접한 나무 사이의 간격을 구한다.
- 3 - 1 = 2, 7 - 3 = 4, 13 - 7 = 6
- 이 간격들의 최대공약수를 구한다.
- 간격을 모두 gcd로 만들면 최소한의 나무로 균등 간격이 된다.
- 전체 거리에서 gcd 간격으로 나무를 심었을 때의 전체 나무를 개산한다.
- 기존에 있던 나무 수를 빼면, 추가로 심어야 할 나무 수가 나온다.
코드
# 백준 2485 - 가로수 # 분류 : 수학 N = int(input()) X = [0] * N for i in range(N) : X[i] = int(input()) def gcd(a, b) : if a < b : a, b = b, a if b == 0 : return a else : return gcd(b, a % b) d = 0 for i in range(N - 1) : d = gcd(d, X[i + 1] - X[i]) print((X[-1] - X[0]) // d + 1 - N)
이 글은
(새창열림)
본 저작자 표시, 비영리 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons
본 저작자 표시
비영리
'Programming > 백준' 카테고리의 다른 글
백준 2491 - 수열 (파이썬) (0) | 2025.03.31 |
---|---|
백준 2506 - 점수계산 (파이썬) (0) | 2025.03.30 |
백준 2527 - 직사각형 (파이썬) (0) | 2025.03.28 |
백준 2460 - 지능형 기차 2 (파이썬) (0) | 2025.03.28 |
백준 2526 - 싸이클 (파이썬) (0) | 2025.03.28 |
댓글
이 글 공유하기
다른 글
-
백준 2491 - 수열 (파이썬)
백준 2491 - 수열 (파이썬)
2025.03.31https://www.acmicpc.net/problem/2491풀이어떤 수열이 주어졌을 때, 연속적으로 커지거나 같거나, 혹은 작아지거나 같은 부분 수열 중 가장 긴 길이를 구하는 문제이다.비내림차순 수열의 최대 길이 계산비오름차순 수열의 최대 길이 계산위 두 결과 중 최대값을 출력A[: : -1] 로 뒤집어서 감소하거나 같은 부분 수열을 구할 수 있도록 바꾼다.시간복잡도 분석비내림차순 수열의 계산 → O(N)비오름차순 수열의 계산 → O(N)즉, O(N)코드# 백준 2491 - 수열# 분류 : 구현N = int(input())A = list(map(int, input().split()))max_count = 1count = 1for i in range(1, N) : if A[i- 1] -
백준 2506 - 점수계산 (파이썬)
백준 2506 - 점수계산 (파이썬)
2025.03.30https://www.acmicpc.net/problem/2506풀이쉬운 문제이다, 각 문제가 연속해서 옳은 정답인 경우 증가하고, 틀린 문제가 있다면 0점으로 초기화 하여, 누적합이 되지 않도록 하는 문제이다.단순히 for문으로 O(N) 시간 복잡도로 문제를 해결할 수 있다.코드# 백준 2506 - 점수계산# 분류 : 구현N = int(input())scores = list(map(int, input().split()))answer = 0score = 0for i in scores : if i == 1 : score += 1 answer += score else : score = 0 print(answer) -
백준 2527 - 직사각형 (파이썬)
백준 2527 - 직사각형 (파이썬)
2025.03.28https://www.acmicpc.net/problem/2527풀이두 직사각형이 주어졌을 때, 겹치는 영역이 어떤 형태인지 판단하는 문제이다.다양한 겹침의 경우를 다음 네가지 중 하나로 분류해야한다.a → 직사각형이 겹치는 경우 (면적으로 겹침)b → 직사각형이 선분으로 겹침c → 꼭짓점만 겹침d → 전혀 겹치지 않음x축 겹침 여부 판단 및 y축 겹침 여부 판단을 진행하면 된다.위에서 구한 x_intersection, y_intersection 값을 조합해서 미리 정의된 결과 테이블에서 문자를 출력하면 답을 쉽게 구할 수 있다.코드# 백준 2527 - 직사각형# 분류 : 기하학answer = [ ['d', 'd', 'd'], ['d', 'c', 'b'], ['d', 'b', 'a']]f… -
백준 2460 - 지능형 기차 2 (파이썬)
백준 2460 - 지능형 기차 2 (파이썬)
2025.03.28
댓글을 사용할 수 없습니다.