[2021 SCPC] 2. 이진수

시간 초과가 떴다 ㅜㅜ

문제

nn 비트로 구성된 이진수 A=a1a2…an, A=a1a2…an (aiai는 0 또는 1)와 자연수 tt 가 주어질 때, AA로부터 아래와 같은 연산을 통해 새로운 이진수 B=b1b2…bnB=b1b2…bn 를 만든다.

요약 : nn비트로 구성된 이진수 AA를 자연수 tt를 사용해 이진수 BB로 바꾸기

예를 들어, 아래 그림에서 보인 것처럼 9 비트로 구성된 이진수 A=100100101 A=100100101 이고 t=2 t=2 인 경우, 변환을 통해 새로운 이진수 B=011011101 B=011011101 을 얻을 수 있다.

변환된 이진수 BB와 자연수 tt가 주어질 때, 이 정보로부터 역으로 AA를 유추하는 프로그램을 작성하고자 한다.
예를 들어, 그림에서 보인 것처럼 B=011011101 B=011011101 이고 t=2 t=2 라면 가능한 AA의 값은 100100101, 100110101, 000110100100100101, 100110101, 000110100 등이다.

주어진 이진수 BB와 자연수 tt로부터 유추 가능한 AA가 둘 이상일 경우, AA의 값을 이진수로 보았을 때, 가장 작은 값을 출력하는 프로그램을 작성하시오. 주어진 이진수 BB와 자연수 tt 로부터 유추 가능한 AA가 존재하지 않는 경우는 주어지지 않는다.


- 제한시간: 전체 테스트 케이스는 64개 이하이며, 전체 수행 시간은 1초 이내. (Java 2초 이내) 
    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
    그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 100MB
- 제출 제한 : 최대 10회

 

메모리 사용 제한

heap, global, static (총계) : 256MB
stack : 100MB

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로  TT개의 테스트 케이스가 주어진다. (1≤T≤64)(1≤T≤64)
각 테스트 케이스의 첫 줄에는 변환된 이진수 B의 비트 수를 나타내는 정수 nn과 자연수 tt가 주어진다. (2≤n≤50,000,1≤t<n)(2≤n≤50,000,1≤t<n)
다음 줄에는 길이가 nn 인 이진수가 주어진다.
주어진 이진수 BB와 자연수 tt로부터 유추 가능한 AA가 존재하지 않는 경우는 주어지지 않는다.

- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 150 점)
   주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
 각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.

ㆍ 그룹 1 (31 점) : 이 그룹의 테스트 케이스에서는 n≤15n≤15이다.
ㆍ 그룹 2 (38 점) : 이 그룹의 테스트 케이스에서는 n≤1,000n≤1,000이다.
ㆍ 그룹 3 (81 점) : 이 그룹의 테스트 케이스에서는 n≤50,000n≤50,000이다.

* 모든 테스트 케이스를 풀지 않고 일부분의 그룹에 속하는 테스트 케이스만을 푸는 경우에도 입력 받은 모든 케이스에 대해 (답이 틀릴지라도) 출력 양식에는 맞는 출력을 생성해야 점수가 반영되는 것이 보장된다.

* 제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며, 그때까지 출력한 내용이 파일에 저장되지 않아 점수가 제대로 반영되지 않을 수 있습니다.

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #CC”를 출력하여야 한다. 이때 CC는 테스트 케이스의 번호이다.
그 다음 줄에, 주어진 이진수 BB와 자연수 tt로부터 유추 가능한 AA중, AA의 값을 이진수로 보았을 때 가장 작은 값을 출력하시오.

 

입출력예

2 5 1 00111 10 2 1111111000

Case #1 00011 Case #2 0111100000

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Answer;

int main(int argc, char** argv)
{
	int T, test_case;
    int n, t;
    vector <int> binary;

	// freopen("input2.txt", "r", stdin);

	cin >> T;
	for (test_case = 0; test_case  < T; test_case++) {
		Answer = 0;

        cin >> n >> t;
        
        for (int i = 0; i < n; n++) {
            cin >> bin;
            binary.push_back(bin);
        }

        // Result vector sort
        Result.sort();

        // Answer = Result[0]
		Answer = Result[0];

		// Print the answer to standard output(screen).
		cout << "Case #" << test_case+1 << endl;
		cout << Answer << endl;
	}

	return 0;
}