[2018 SCPC 2차 예선]
지진은 인간이 어떻게 할 수 없는 큰 재앙이며, 예측이 매우 어렵다.
김박사는 삼성전자의 후원을 받아서 인류의 복지를 위해 지진을 예측하는 연구를 진행하고 있다.
이 연구가 성공한다면 인류는 더 이상 지진을 두려워할 필요가 없다.
연구를 수행하기 위해, 지진이 매우 자주 발생하는 섬에 지진파 탐지기를 설치했다.
이 탐지기는 매일매일 그날 탐지한 지진파의 세기를 측정하여, 가장 큰 값을 서버로 전송한다.
이 값은 1 이상 10,000 이하의 정수이다. 김박사는 지난 \(N\) 일 동안의 지진파를 연구해본 결과, 연속된 \(M\)일 측정된 지진파의 세기가 특정한 패턴을 보인다면 지진의 확률이 높다는 중간 결과를 얻어냈다.
이 패턴은, 지진파 각각의 값 보다는, \(M\)일동안 지진파의 세기 순서와 관계가 있다.
예를 들어 \(M=5\)일 때 이 패턴이 1 6 3 2 4라면, 정확하게 이 값이 나올 때 지진이 일어나는 것이 아니라 \(M\)일간 측정된 지진파의 세기의 크기 순서가 패턴의 크기의 상대적인 순서와 같다면, 즉 13 72 37 19 65와 같다면 마지막 측정값이 65인 날 지진이 일어날 확률이 높다는 뜻이다. 같은 수치가 패턴에 두 번 이상 나오는 경우는 없다.
이 성과가 일반적인 것인지 여부를 판정하기 위해서 다른 곳에서 측정한 지진파 데이터와 비교를 통해서 확인을 해보았다.
이 결과로 알게 된 것은, 전체적으로는 이 접근 방법이 맞지만 실제로는 정확하게 일치하지 않는데 지진이 일어난 경우가 있었다.
데이터를 확인해보니, 연속한 \(M\)일간의 지진파를 패턴과 대조할 때, 지진파와 패턴에서 동일한 최대 \(K\)일의 데이터를 제외하고 남은 데이터의 상대적인 순서가 일치한다면 지진이 일어날 수 있다는 것을 알게 되었다.
위의 예에서 \(K=2\)이고, \(M=5\)일간의 데이터가 97 72 35 19 43일 경우, 이 데이터를 상대적인 순서대로 나열하면 5 4 2 1 3이므로 패턴 1 6 3 2 4와 일치하지 않는다.
하지만 5일간의 데이터에서 첫번째 날의 데이터를 제외하고 생각해보면, 데이터는 72 35 19 43이고 패턴은 6 3 2 4가 되어 모두 크기 순서가 4 2 1 3으로 일치하게 된다.
또, 패턴이 5 2 1 4 3이라면, 두번째 날과 네번째 날의 데이터를 제외하고 생각해보면, 데이터는 97 35 43, 패턴은 5 1 3으로 모두 크기 순서가 3 1 2로 일치하게 된다.
연속한 \(M\)일을 어떻게 잡더라도, 이 기간 중 같은 값이 두 번 이상 나오는 경우는 존재하지 않는다.
제외할 수 있는 날은 \(M\)일 중 어느 날도 가능함에 주의하라. 패턴이 반드시 1부터 \(M\) 사이의 숫자로만 될 필요는 없다.
\(N\)일간의 지진파 측정 값, 지진이 일어날 가능성을 나타내는 \(M\)일의 패턴, \(K\)가 주어졌을 때 주어진 데이터로부터 지진이 일어날 수 있는 횟수를 구하는 프로그램을 작성하시오.
같은 날에 지진이 일어난다고 데이터를 해석할 수 있는 방법이 둘 이상 있더라도 지진이 일어날 수 있는 횟수는 한번으로 센다.
- 제한시간: 전체 테스트 케이스는 30개 이하이며, 전체 수행 시간은 3초 이내. (Java 6초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 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)), (M) ((1≤M≤300), (M≤N)), (K) ((0 ≤K<M))이 순서대로 주어지며 각각은 측정한 지진파 데이터의 크기, 패턴의 길이, 허락할 수 있는 최대 오차를 나타낸다.
다음 줄에는 (N) 일간 측정한 지진파 데이터가 주어진다. 이는 (N)개의 정수로 표현되는데, 각각의 수는 1 이상 10,000 이하이다..
그 다음 줄에는 지진이 일어날 때 지진파의 패턴을 나타내는 (M)개의 정수가 주어진다. 각각의 수는 1 이상 10,000 이하이다.
- 점수 : 최대 10회 제출하여 취득한 각각의 점수 중에서 최대 점수 (만점 250점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (39 점) : 이 그룹의 테스트 케이스에서는 (K=0)이다.
ㆍ 그룹 2 (102 점) : 이 그룹의 테스트 케이스에서는 (N ≤ 1,000) , (M ≤ 50)이다.
ㆍ 그룹 3 (109 점) : 이 그룹의 테스트 케이스에서는 별도의 제한이 없다.
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다.
이때 C는 테스트 케이스의 번호이다.
그 다음 줄에 입력으로 받은 지진파 데이터에서 지진이 일어날 수 있는 횟수를 출력한다.
| 입력 |
|---|
| 2 7 5 1 1 6 5 3 7 2 4 1 5 3 2 4 8 4 1 1 3 5 7 9 11 13 15 1 4 2 3 |
| 출력 |
|---|
| Case #1 1 Case #2 5 |