프론트엔드 개발자 중규리 입니다 ദി ᷇ᵕ ᷆ ) 자세히보기

PS/문제풀이

백준 17266 어두운 굴다리 Python

중규리 2024. 1. 7. 11:39

🐸 문제 정보

 

17266번: 어두운 굴다리

인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙

www.acmicpc.net

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

29.04m

 

📝 풀이

실버 4 문제였음에도 초반에 구현 방법을 잘못 설정하여 시간이 오래 걸렸다.

왼쪽 가로등과 비교하는 형식으로 구현했다가, 이렇게 되면 오른쪽 가로등과의 최적의 길이를 구할 수 없었다.

고친 풀이 방법은 아래와 같다.

 

  1. 가로등 시작 위치와 끝 위치는 각각 0과 m과 차이를 비교해야함
  2. 두 번째 가로등부터는 이전 가로등과 사이의 중간 값을 올림하여, 현재 저장된 가로등과 최대값으로 갱신

 

🧑‍💻 나의 답

# pypy3

import sys
import math
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
x = list(map(int, input().rstrip().split()))

res = x[0]
for i in range(1, m):
    res = max(res, math.ceil((x[i] - x[i - 1]) / 2))
res = max(res, n - x[-1])

print(res)

'PS > 문제풀이' 카테고리의 다른 글

백준 1166 선물 Python  (0) 2024.01.08
백준 2512 예산 Python  (1) 2024.01.07
백준 3165 5 Python  (1) 2024.01.06
백준 15724 주지수 Python  (1) 2024.01.06
백준 6068 시간 관리하기 Python  (1) 2024.01.06