[백준/Python] 24229번: 모두싸인 출근길

문제

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

24229번: 모두싸인 출근길

---

문제 요약

[L, R]의 범위에 놓여진 n개의 판자를 통해 이동할 수 있는 다리의 가장 먼 지점을 출력한다.

+ 다리는 수직선으로 나타낼 수 있다.

 

판자로 덮이지 않은 좌표는 점프를 통해 건널 수 있으며, 점프를 할 경우, 착지한 위치에 판자가 높여 있어야 한다.

 

한 번의 점프로 건너갈 수 있는 최대 거리는 마지막으로 착지한 시점 이후로 건너간 거리와 같다.

 

+ 판자의 양 끝점에도 착지가 가능하다.

+ 점프를 했는데 판자 위에 착지하지 못한 경우는 이동하지 않은 것으로 간주한다.

---

코드

N = int(input()) # 판자들의 개수

# # 판자들의 위치 정보 입력 [(왼쪽 끝 칸, 오른쪽 끝 칸)]
arr = [tuple(map(int, input().split())) for _ in range(N)]
arr.sort() # 순서대로 이어 붙이기 위해 정렬 

boards = [] # 이어 붙인 판자들의 위치 정보를 저장하는 배열
left, right = 0, 0
for i in range(N):
    if i == 0: # 첫 판자 정보는 일단 저장
        left, right = arr[i] # 언패킹
    else:
        # 현재 판자와 다음 판자가 겹칠 경우
        if right >= arr[i][0]: 
            right = max(right, arr[i][1]) # 오른쪽 판자의 위치 갱신 (이어 붙임)
        # 현재 판자와 다음 판자가 겹치지 않을 경우
        else:
            boards.append((left, right)) # 현재 판자는 더 이상 변경되지 않으므로 저장
            left, right = arr[i] # 다음 판자와 겹치는 다른 판자가 있는지 탐색
             
boards.append((left, right)) # 마지막 판자는 따로 저장

max_right = 0 # 최대 점프 가능 거리
idx = 0 # 갈 수 있는 판자의 인덱스 

for i in range(len(boards)):
    # 점프로 이동 가능한 범위 내에 있는 판자라면
    if max_right >= boards[i][0]:
        idx = i # 판자 인덱스 저장
        
        # 최대 점프 가능 거리 갱신
        max_right = max(max_right, boards[i][1] + (boards[i][1] - boards[i][0])) # (boards[i][1] - boards[i][0]는 판자 길이

print(boards[idx][1])

---

코드 설명

1. 연결된 판자들은 하나의 판자로 간주할 수 있으므로 서로 이어 붙인다.

 

2. 왼쪽에 있는 판자부터 접근하여, 다음 판자의 왼쪽 끝 좌표를 최대 점프 가능 거리와 비교하여 이동 가능한 범위 내 판자를 판별하고, 최대 점프 가능 거리를 갱신한다.

+ 왼쪽에 있는 판자부터 접근을 위해 먼저 정렬한다.

 

3. 최대 점프 가능 거리가 아닌, 가장 오른쪽에 있는 이동 가능한 판자의 오른쪽 끝 점 좌표를 출력한다.