시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 212 | 90 | 69 | 43.125% |
괴도 인하는 인하대학교의 수많은 동아리들이 두려워하는 악명 높은 도둑이다. 그는 동아리방에 남겨진 값비싼 물건들을 아무도 모르게 훔쳐 간다. 특이하게도 범행 전 늘 예고장을 보내지만, 워낙 신출귀몰한 탓에 모습이 목격된 적조차 없다.
IGRUS 동방의 보물 한정판 게임기 역시 괴도 인하의 눈을 피할 순 없었다. 범행 예고장을 받은 IGRUS 부원들은 게임기를 지키기 위해 동방에 다음과 같은 보안 시스템을 설치하였다.
다음 날 아침, 보안 시스템은 꺼져 있고 카메라 몇 개가 부서져 있었다. 물론 알람도 울리지 않았다. 부원들은 서둘러 게임기를 확인했지만 게임기 대신 쪽지 한 장 만이 남겨져 있었다.
감시 카메라들을 망가뜨려 미안합니다. 대신 알람을 울리지 않고 게임기를 가져가는데 필요한 최소한의 카메라만 부수었으니 금방 복구할 수 있겠죠? - 괴도 인하
IGRUS의 회장 여준이는 괴도 인하가 동방의 입구에서 출발해 오른쪽과 아래쪽으로만 이동해 보안 시스템을 끄는 스위치에 도달하기 위해 몇 개의 카메라를 부수었는지 궁금해졌다. 동방의 크기와 K개의 감시 카메라의 정보가 주어지면, 괴도 인하가 몇 개의 감시 카메라를 부수었는지 출력하는 프로그램을 작성해보자.
첫 번째 줄에 괴도 인하가 지나가야 하는 방의 행의 개수와 열의 개수 N과 M이 주어진다.
두 번째 줄에 방에 존재하는 감시 카메라의 개수 K가 주어진다.
세 번째 줄부터 K개의 줄에 걸쳐 각 감시 카메라에 대해 감시 구역의 왼쪽 위 좌표 ai, bi와 오른쪽 아래 좌표 ci, di가 공백으로 구분되어 주어진다.
주어진 방을 알람을 울리지 않고 통과하기 위해 괴도 인하가 부수어야 할 감시 카메라의 최솟값을 출력한다.
4 5 4 2 2 4 4 1 4 2 5 3 1 3 2 2 3 4 3
1
다음 그림과 같은 경로로 움직이면 감시 카메라를 하나만 부수고 게임기를 훔칠 수 있다.
2 2 3 2 2 2 2 2 2 2 2 2 2 2 2
3
어떤 경로로 움직이든 3개의 감시 카메라를 부숴야 한다.
University > 인하대학교 > 2022 IGRUS Newbie Programming Contest K번