[백준 17266번] 파이썬 - 어두운 굴다리

백준 17266 - 어두운 굴다리

시간 제한 1초, 메모리 제한 256MB

# 조건

• 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다.
• 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다.
• 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다.
• 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다.
• 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정을 끝냈다.
• 그리고 각 가로등은 높이만큼 주위를 비출 수 있다.
• 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을수록 가격이 비싸지기 때문에 최소한의 높이로 굴다리 모든 길 0~N을 밝히고자 한다.
• 최소한의 예산이 들 높이를 구하자.
  • 단 가로등은 모두 높이가 같아야 하고, 정수이다.
• 다음 그림을 보자.

• 다음 그림은 예제 1에 대한 설명이다.

• 가로등의 높이가 1일 경우 0~1사이의 길이 어둡기 때문에 상빈이는 지나가지 못한다.
• 아래 그림처럼 높이가 2일 경우 0~5의 모든 길이 밝기 때문에 상빈이는 지나갈 수 있다.

입력

• 첫 번째 줄에 굴다리의 길이 N 이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에 가로등의 개수 M 이 주어진다. (1 ≤ M ≤ N)
• 다음 줄에 M 개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 ≤ x ≤ N)
• 가로등의 위치 x는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

출력

• 굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이를 출력한다.

# 접근 방법

• 한 지점은 양쪽의 가로등이 절반 이상씩 비추면 되므로
  • 각 가로등 사이의 거리 // 2 + (1 if dist % 2 == 1 else 0)을 통해 dist 배열에 저장해준다.
• 또한 0과 N에도 가로등의 영향이 끼쳐야 하는데 제일 앞과 제일 뒤는 // 2가 아닌 arr[0], N - arr[-1]을 하여 추가해준다.
• 이후 구한 dist 값 중 최댓값을 뽑으면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
M = int(input())  
dist = [0] * (M+1)  
arr = [*map(int, input().split())]  
dist[0] = arr[0]  
dist[-1] = N - arr[-1]  
for i in range(M-1):  
    val = arr[i+1] - arr[i]  
    dist[i+1] = val//2 + (1 if val % 2 else 0)  

print(max(dist))

• 이걸 조금 더 간결하게 표현한 다른 분의 코드이다.
• 리스트 컨프리헨션을 잘 사용하는 것이 파이써닉하기에 연습을 많이 해볼 필요가 있을 것 같다.

D = int(input())
N = int(input())

nums = list(map(int,input().split()))

dist = [ nums[0]]+[ (nums[i]-nums[i-1]+1)//2 for i in range(1,N)]+[D-nums[-1]]

print(max(dist))

• 또한, 알고리즘 문제를 풀다보면 zip함수를 사용하여 2개의 배열을 합쳐서 푸는 경우가 많은데 zip함수는 매우 유용해보이기에 잘 참고해서 사용해보자!

n, _, *nums = map(int, sys.stdin.buffer.read().split())  
m = max((a - b + 1 for a, b in zip(nums[1:], nums)), default=0)  
print(max(int(m / 2), nums[0], n - nums[-1]))