백준 14595번: 동방 프로젝트 (Large) [Python]

작성일 | In
골드 IV 골드 IV

문제

동방 프로젝트 (Large)

풀이

만약 두 행동의 구간이 겹친다면 결국 하나의 방이 될 것이므로 구간이 겹치지 않는 경우를 체크해주면 됩니다.

$i$번째 행동을 $(x_i, y_i)$로 나타냅시다. $x_i$가 증가하는 순서대로 정렬하고 스위핑해서 해결할 수 있습니다.

현재까지 세었던 방 중 방의 끝 중 가장 오른쪽 칸을 $end$, 이때까지 센 방의 개수를 $cnt$라 하고 둘 모두 초기에 $0$으로 설정합시다.

만약 $end < x_i$인 경우 $x_i$가 증가하도록 정렬했으므로 더 이상 구간 $[end + 1, x_i - 1]$에는 벽을 부수는 행동이 존재하지 않습니다. 따라서 $end + 1$부터 $x_i - 1$까지는 한 칸씩 방이 되고, $x_i$부터 새로운 방이 됩니다. 따라서 $cnt$에 $end - x_i$를 더해줍니다.

이후에 매번 $end = \max(end, y_i)$로 방의 가장 오른쪽을 갱신해주면 됩니다.

모든 스위핑을 마치고 나면 $cnt$가 답이 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def main():
    N = int(input())
    M = int(input())

    actions = [tuple(map(int, input().split())) for _ in range(M)]
    actions.sort()

    cnt = 0
    end = 0
    for x, y in actions:
        if end < x:
            cnt += x - end
        end = max(end, y)

    cnt += N - end

    print(cnt)


main()

백준 14595번: 동방 프로젝트 (Large) [Python]