시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 748 | 355 | 297 | 48.929% |
마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 $N$마리를 집에서 키우기로 결심했다!
호무라는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.
그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 $M$개의 닫힌구간들 ${[L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]}$ 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!
이를 명심하면서, 호무라는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 $N$마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!
첫 번째 줄에 키우기를 원하는 강아지의 수 $N (2\leq N\leq 100\,000)$, 제약 사항에 해당하는 닫힌구간의 개수 $M (1\leq M\leq 100)$, 그리고 $A$와 $B (1\leq A,B\leq N)$가 띄어쓰기로 구분되어 주어진다. 그 다음 $M$줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. $1\leq i\leq M$에 대하여 $L_i$와 $R_i$는 $1$ 이상 $N-1$ 이하의 정수이며, $L_i\leq R_i$이다.
첫 번째 줄에 정확히 $N$마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 $-1$을 출력한다.
7 1 2 3 3 4
3
초기 상태($0$마리) $\rightarrow$ $2$-생성 마법($2$마리) $\rightarrow$ $3$-생성 마법($5$마리) $\rightarrow$ $2$-생성 마법($7$마리) 순서로 $7$마리의 강아지를 집에 들일 수 있다.
8 2 5 4 1 2 1 3
2
초기 상태($0$마리) $\rightarrow$ $4$-생성 마법($4$마리) $\rightarrow$ $4$-생성 마법($8$마리) 순서로 $8$마리의 강아지를 집에 들일 수 있다.
8 1 2 5 6 7
-1
조건을 만족하면서 $8$마리의 강아지를 집에 들일 수 있는 방법은 존재하지 않는다.
Contest > BOJ User Contest > 와쿠(AGCU)컵 > 제1회 와쿠(AGCU)컵 M번