백준 17266: 어두운 굴다리 (Python)

임동혁 Ldhbenecia·2024년 2월 6일

구현 백준

Algorithm

목록 보기

8/16

BOJ 17266 어두운 굴다리

💡 실버 4인데 정답률이 39%이다.
쉽지않을걸 예상하고 풀이에 들어가고 두 가지 방식으로 풀었다.

정답 코드

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

result = []

if m == 1 and x[0] == 0:
  print(n)
else:
  for i in range(len(x)):
    if not result:
      result.append(x[i])
    else:
      result.append((x[i] - x[i-1] + 1) // 2)

  if x[-1] != n:
    result.append(n - x[-1])
    
  print(max(result))

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

result = []
max_distance = max(x[0], n - x[-1])
result.append(max_distance)

for i in range(1, m):
  distance = (x[i] - x[i - 1] + 1) // 2
  result.append(distance)

print(max(result))

풀이과정

입력 예시가 주어졌는데 주어진 입력 예시만으로는 풀이를 하는데 어려움이 있었다.

10
3
2 4 6

10
3
2 4 9

이 두 가지의 입력 예시를 추가로 생성하였다.
이 입력 예시의 차이점은 2 4 6의 경우 가장 마지막 구간인 4가 정답이고
2 4 9인 경우 가장 마지막 구간은 1이 나오기 때문에 앞에서 기둥 사이의 거리를 추출해내야한다.

첫 번째 코드 풀이

조건에서 x에 대한 입력은 오름차순으로 입력받는 다는 것을 보고 이진탐색으로 처음 시도하였으나 뇌사와서 포기하였다.

그래서 우선 입력 예시 2번을 처리했다.
1. 기둥이 1개 주어진다.
2. 그 기둥이 0번 위치에 존재할 경우 n이 정답

나머지 예시의 경우
1. result라는 리스트를 하나 생성한다.
2. 제일 처음 시작점 0부터 첫 기둥까지의 길이를 삽입한다.
3. 그 다음은 수식을 사용하였다. 24 ~ 75번까지 있다고 치면 총 문제 수는 75 - 24 + 1로 풀이하기 때문에 이렇게 사이의 거리를 구한다. 그리고 2로 나누어서 중간점을 찾으면 된다.
아래 이미지는 A4 용지에 대충 처음에 그린건데 중간에 3이라는 것을 볼 수 있다.
4와 9사이의 거리는 9 - 4 + 1해서 6이고 이를 절반으로 나누면 3이 되는 것을 확인할 수 있다.

4. 그리고 마지막 기둥의 오른쪽 남은 부분을 삽입한다.
5. 이 중 가장 큰 값이 정답

두 번째 코드 풀이

훨씬 깔끔한 방법이다.
1. result라는 리스트를 하나 생성한다.
2. 가장 큰 값이 정답이기 때문에 최장 길이 변수를 하나 선언한다.
초기 값은 시작점 0부터 첫 기둥의 거리, 마지막 기둥부터 끝점까지의 거리 중 하나이다.
3. 반복문을 순회하며 x리스트에 주어진 길이를 넣어주면 끝난다.

두 번째 풀이가 훨씬 깔끔하고 첫 번째 풀이 코드에서 불필요한 부분들을 제거한 모습을 확인할 수 있다.