[2018 SCPC 2차 예선]
메모지
평면 상에 메모지가 필요한 \(N\)개의 점들 \(p_i=(x_i,y_i)\)가 주어진다.
단, 평면상의 임의의 수평선에 두 점 이상이 놓여 있지 않다고 가정한다. 다시 말해서, 모든 점들의 \(y\) 좌표는 서로 다르다.
각 점을 설명하는 내용을 수직과 수평 변을 가지는 사각형 모양의 메모지에 기록할 것이다.
메모지의 수직 변의 길이를 높이라 하고 수평 변의 길이를 너비라고 하면 모든 메모지의 너비는 동일하고 높이는 각기 다를 수 있다.
그림 1.
\(N\)개의 점들 \(p_i\)를 모두 포함하는 수직과 수평 변을 가지는 사각형 영역 \(R\)을 그린다.
그러면 사각형 영역 \(R\)의 오른편 밖으로, 다시 말해서, \(R\)의 오른쪽 변의 오른쪽으로 메모지를 붙일 것이다.
또한 메모지의 왼쪽 변은 모두 같은 \(x\) 좌표를 가진다. 따라서 이 좌표는 \(R\)의 오른쪽 변의 \(x\) 좌표보다는 항상 크다.
메모지들은 서로 겹치게 붙일 수 없다. 단, 메모지들의 변만 서로 겹치는 경우는 가능하다.
또한 메모지를 붙일 때, 메모지의 수직, 수평 변이 각각 평면 상에 수직, 수평이 되도록 붙일 것이다.
그리고 메모지들을 붙이는 순서는 아래에서 위쪽 방향으로 대응되는 점들의 순서와 일치한다.
메모지들을 붙인 후 점 \(p_i\)의 메모지임을 표시하기 위해서 점과 메모지를 연결하는 표시 선을 그릴 것이다.
표시 선은 단지 두 가지 모양뿐이다. 수평-수직-수평선의 모양이거나 단지 수평선만으로 이루어진다.
수평-수직-수평선의 모양인 경우를 꺾인 표시 선 이라고 한다.
특히 꺾인 표시 선인 경우 점에서 출발해서 수평으로 사각형 R 의 오른쪽 변을 통과해서 그린 후 수직-수평 부분을 그려서 메모지와 연결한다 (그림 1).
이 때, 수평선만으로 된 표시 선이나 꺾인 표시 선의 마지막 수평선 부분이 메모지 왼쪽 변의 어느 부분에 닿아도 상관이 없으며,
특히 메모지의 수평 변과 같은 \(y\)좌표를 가지는 경우도 연결된 것이다.
또한 메모지를 붙이는 순서가 (아래에서 위쪽 방향으로) 대응되는 점들의 순서와 일치함으로 표시 선들을 항상 서로 교차하지 않게 그릴 수 있다.
점들의 좌표와 메모지들의 높이가 주어질 때, 꺾인 표시선의 개수가 최소가 되도록 메모지들을 붙이고 싶고 이 경우 최소 개수를 출력하는 프로그램을 작성하시오.
- 제한시간: 전체 테스트 케이스는 30개 이하이며, 전체 수행 시간은 2초 이내. (Java 4초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.println"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 30\))
각 테스트 케이스의 첫 줄에는 점들의 개수를 나타내는 한 개의 정수 \(N\) (\(1≤N≤10,000\))이 주어진다.
다음 이어지는 \(N\) 개의 줄 각각에는 한 점의 \(x\)좌표와 \(y\)좌표를 나타내는 두 개의 정수 \(X,Y\) (\(0≤X, Y≤10^9\))와 그 점의 메모지의 높이를 나타내는 정수 \(H\) (\(1≤H≤10,000\))가 순서대로 주어진다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 150점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (49점) : 이 그룹의 테스트 케이스에서는 \(N≤100\) 이다.
ㆍ 그룹 2 (32점) : 이 그룹의 테스트 케이스에서는 \(N≤1,000\) 이다.
ㆍ 그룹 3 (69점) : 이 그룹의 테스트 케이스에서는 별도의 제한이 없다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다.
이때 C는 테스트 케이스의 번호이다.
그 다음 줄에 최소 꺾인 표시선의 개수를 출력하시오.
입출력예
| 입력 |
|---|
| 2 3 1 3 1 3 1 1 2 2 2 5 1 5 1 3 3 1 4 2 3 2 4 1 5 1 1 |
| 출력 |
|---|
| Case #1 0 Case #2 1 |