[2018 SCPC 본선]
외계메시지
외계인이 존재하는가는 사람들이 오랫동안 궁금해온 문제이다.
김박사는 삼성전자의 후원을 받아서 특정한 별에 외계인이 존재하는지 연구를 진행하고 있다.
이 연구로 외계인을 발견한다면 인류의 모든 지식에 큰 변화가 올 것이다.
이 별이 연구의 대상이 된 이유는 별의 밝기가 매 시간마다 변하기 때문이다.
처음에는 단순한 변광성으로 생각하였지만, 그러기에는 밝기의 변화에 반복이 자주 발생한다는 것을 알아냈기에 현재로서는 이 별에 고도의 문명이 존재하여, 별의 밝기를 조절할 수 있다는 의견이 대다수이다.
고성능 전파망원경 하나가 이 별을 쫓아다니면서 매 시간마다 별의 밝기를 기록한다.
이 밝기는 1 이상 255 이하의 정수로 정규화되어 기록된다.
매 시간 별의 밝기를 기록한 개의 정수가 주어졌을 때, 김박사는 이 밝기의 변화가 우연인지 아닌지 알기 위해서 번 이상 반복되어 나오는 패턴이 있는지를 효율적으로 찾고 싶어 한다.
예를 들어, 이고 2, 1, 4, 1, 4, 1이 전파망원경의 입력이라고 하자.
라고 하면, 입력 중 두 번 이상 나오는 패턴을 찾아보면 길이가 1인 패턴은 1, 4, 길이가 2인 패턴은 1, 4 그리고 4, 1, 길이가 3인 패턴은 1, 4, 1이다.
김박사의 생각으로는 연속하여 나타나면서 두번 이상 나타나는 가장 긴 패턴이 가장 큰 의미를 갖는다.
따라서 이 경우 답은 1, 4, 1이다.
1, 4, 1이 두 번 나타날때 서로 교차할 수 있는데 주의하라.
이라면 세 번 이상 반복되어 나온 패턴은 1 뿐이며, 라고 하면 만족하는 패턴이 없다.
구체적으로 어떤 패턴이 나타나는지보다 이 패턴의 길이가 더 의미가 크기 때문에,
일때 원하는 답은 3 (만족하는 패턴이 1, 4, 1), 일때 원하는 답은 1 (만족하는 패턴이 1), 일때 원하는 답은 0 (만족하는 패턴이 없음)이다.
시간의 별의 밝기 측정 값, 패턴의 반복 횟수 가 주어졌을 때, 번 이상 반복하여 나타나는 패턴 중 가장 긴 패턴의 길이를 구하는 프로그램을 작성하시오.
- 제한시간: 전체 테스트 케이스는 50개 이하이며, 전체 수행 시간은 0.5초 이내. (Java 1초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,
이후 차례로 개의 테스트 케이스가 주어진다. ()
각 테스트 케이스의 첫 줄에는 두 개의 정수 , 이 순서대로 주어지며 각각은 측정한 별의 밝기 데이터의 크기, 패턴이 나타나야 하는 최소 횟수를 나타낸다.
다음 줄에는 일간 측정한 별의 밝기 데이터가 주어진다.
이는 개의 정수로 표현되는데, 각각의 수는 1 이상 255 이하이다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 197점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (43 점) : 이 그룹의 테스트 케이스에서는 .
ㆍ 그룹 2 (47 점) : 이 그룹의 테스트 케이스에서는 .
ㆍ 그룹 3 (53 점) : 이 그룹의 테스트 케이스에서는 .
ㆍ 그룹 4 (54 점) : 이 그룹의 테스트 케이스에서는 별도의 제한이 없다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.
그 다음 줄에 입력으로 받은 별의 밝기 데이터에서 주어진 횟수 이상 나타나는 가장 긴 문자열의 길이를 출력한다.
만약 조건을 만족하는 문자열이 없다면, 숫자 0을 출력한다.
입출력예
| 입력 |
2
6 2
2 1 4 1 4 1
6 4
2 1 4 1 4 1 |
돌아가기