전구 토글 패턴
브론즈 I의견: 0
일렬로 놓인 \(N\)개의 전구가 있다. 전구는 \(1\)번부터 \(N\)번까지 번호가 매겨져 있으며, 처음에는 모두 꺼져 있다.
이제 \(M\)개의 명령이 차례대로 주어진다. 각 명령은 두 정수 \(l\), \(r\)로 이루어져 있으며, \(l\)번부터 \(r\)번까지의 전구 상태를 모두 뒤집는다. 즉 켜져 있던 전구는 꺼지고, 꺼져 있던 전구는 켜진다.
모든 명령을 순서대로 적용한 뒤, 켜져 있는 전구의 개수를 구하는 프로그램을 작성하라.
예를 들어 \(N = 5\)이고 명령이 \([1, 3]\), \([2, 5]\), \([3, 4]\)로 주어지면 전구의 상태는 다음과 같이 변한다.
[초기] 0 0 0 0 0
[명령 1] 1 1 1 0 0
[명령 2] 1 0 0 1 1
[명령 3] 1 0 1 0 1
따라서 켜진 전구는 \(3\)개이다.
\(1 \le N \le 1{,}000{,}000\)
\(0 \le M \le 1{,}000{,}000\)
\(1 \le l \le r \le N\)
첫째 줄에 전구의 개수 \(N\)과 명령의 개수 \(M\)이 공백으로 구분되어 주어진다 (\(1 \le N \le 1{,}000{,}000\), \(0 \le M \le 1{,}000{,}000\)).
다음 \(M\)개의 줄에는 각각 두 정수 \(l\), \(r\)가 주어진다 (\(1 \le l \le r \le N\)). 이는 \(l\)번부터 \(r\)번까지의 전구를 모두 뒤집는 명령이다.
모든 명령을 적용한 뒤 켜져 있는 전구의 개수를 한 줄에 출력한다.
5 3
1 3
2 5
3 4
3
초기 상태는 모두 꺼짐(0 0 0 0 0)이다.
[명령 1] 1~3 뒤집기 → 1 1 1 0 0
[명령 2] 2~5 뒤집기 → 1 0 0 1 1
[명령 3] 3~4 뒤집기 → 1 0 1 0 1
마지막에 켜진 전구는 1, 3, 5번으로 모두 3개이다.
4 1
1 4
4
1~4 전체를 한 번 뒤집으면 0 0 0 0 → 1 1 1 1 이 되어 4개가 켜진다.
3 2
1 2
1 2
0
같은 구간 1~2를 두 번 뒤집으면 원래 상태로 돌아와 켜진 전구가 하나도 없다.
riseoj 작성
출처 Original
평가 및 의견
전구 토글 패턴
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
전구 토글 패턴