이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

백준 2485 - 가로수 (파이썬)

포렌식 & 개발 이야기 - Forensics & Development

백준 2485 - 가로수 (파이썬)

  • 2025.03.30 16:24
  • Programming/백준
글 작성자: pental

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

풀이

가로수들이 일정하지 않은 간격으로 심어져 있다. 이 간격을 모두 같게 만들기 위해 새로운 나무들을 더 심어야한다.

  • 현재 심어진 가로수의 좌표가 주어진다.
  • 추가로 심어야 하는 나무의 수를 구하는 문제이다.

풀이과정은 다음과 같다.

  1. 각 인접한 나무 사이의 간격을 구한다.
    1. 3 - 1 = 2, 7 - 3 = 4, 13 - 7 = 6
  2. 이 간격들의 최대공약수를 구한다.
    1. 간격을 모두 gcd로 만들면 최소한의 나무로 균등 간격이 된다.
  3. 전체 거리에서 gcd 간격으로 나무를 심었을 때의 전체 나무를 개산한다.
  4. 기존에 있던 나무 수를 빼면, 추가로 심어야 할 나무 수가 나온다.

코드

# 백준 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

댓글

포렌식 & 개발 이야기 - Forensics & DevelopmentPental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

댓글을 사용할 수 없습니다.

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 2491 - 수열 (파이썬)

    백준 2491 - 수열 (파이썬)

    2025.03.31
    https://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.30
    https://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.28
    https://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
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 방명록

카테고리

  • Category (477)
    • Forensics (19)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (25)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (285)
      • C (10)
      • Python (11)
      • 백준 (231)
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

인기 글

공지사항

태그

  • Forensics
  • axiom
  • 포렌식
  • 디지털포렌식
  • 파이썬
  • 백준
  • pental
  • 프로그래머스
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.