3882번 - 스무고개 출처다국어

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 43 9 7 38.889%

문제

어떤 방에 n개의 물건이 있고, 각 물건은 특징을 가지고 있다. 각 특징은 예 또는 아니오로 대답할 수 있는 질문이다.

특징은 총 종류가 m개가 있다. 이러한 특징을 이용하면 이 방에 있는 모든 물건을 설명할 수 있다. 즉, 모든 물건은 길이가 일정한 불리언 수열로 나타낼 수 있다. 모든 물체는 다른 물체와 적어도 한 특징이 다르다.

상근이는 어떤 물체를 확인하려고 한다. 따라서, 그 물체의 특징을 알고 있는 사람에게 질문을 할 것이다. 모든 질문은 특징 중 하나이고, 모든 답변은 예 또는 아니오이다. 상근이는 답변을 들은 후에 다음 질문을 고를 수 있다.

상근이는 질문은 하나 할 때 마다 100원씩 내야 한다. 주머니 사정이 넉넉하지 않은 상근이는 돈을 가능한 적게 내려고 한다. 상근이는 모든 물체의 특징을 알고 있다. 하지만, 찾으려고 하는 물체의 특징은 알고 있지 못한다. 따라서, 상근이는 질문을 하기 전에 전략을 세울 수 있다.

물체의 특징이 주어졌을 때, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 특징의 개수 m과 물체의 개수 n이 주어진다. (0 < m ≤ 11, 0 < n ≤ 128) 다음 n개의 줄에는 각 물체의 특징이 주어진다. 특징은 길이가 m인 이진 문자열로 각 값은 1(예) 또는 0(아니오)이다. 두 물체의 특징이 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 출력한다. 가능한 질문을 적게 해야 한다.

예제 입력 1 

8 1
11010101
11 4
00111001100
01001101011
01010000011
01100110001
11 16
01000101111
01011000000
01011111001
01101101001
01110010111
01110100111
10000001010
10010001000
10010110100
10100010100
10101010110
10110100010
11001010011
11011001001
11111000111
11111011101
11 12
10000000000
01000000000
00100000000
00010000000
00001000000
00000100000
00000010000
00000001000
00000000100
00000000010
00000000001
00000000000
9 32
001000000
000100000
000010000
000001000
000000100
000000010
000000001
000000000
011000000
010100000
010010000
010001000
010000100
010000010
010000001
010000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
100000000
111000000
110100000
110010000
110001000
110000100
110000010
110000001
110000000
0 0

예제 출력 1 

0
2
4
11
9
W3sicHJvYmxlbV9pZCI6IjM4ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWJiMzRcdWFjZTBcdWFjMWMiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzViNFx1YjVhNCBcdWJjMjlcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWJiM2NcdWFjNzRcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViYjNjXHVhYzc0XHVjNzQwIFx1ZDJiOVx1YzlkNVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMmI5XHVjOWQ1XHVjNzQwIFx1YzYwOCBcdWI2MTBcdWIyOTQgXHVjNTQ0XHViMmM4XHVjNjI0XHViODVjIFx1YjMwMFx1YjJmNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzljOFx1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMmI5XHVjOWQ1XHVjNzQwIFx1Y2QxZCBcdWM4ODVcdWI5NThcdWFjMDAgbVx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHViYTc0IFx1Yzc3NCBcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWFjNzRcdWM3NDQgXHVjMTI0XHViYTg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIFx1YmIzY1x1YWM3NFx1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjNzdjXHVjODE1XHVkNTVjIFx1YmQ4OFx1YjlhY1x1YzViOCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWIyOTQgXHViMmU0XHViOTc4IFx1YmIzY1x1Y2NiNFx1YzY0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1ZDJiOVx1YzlkNVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YjRcdWI1YTQgXHViYjNjXHVjY2I0XHViOTdjIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM5YzhcdWJiMzhcdWM3NDAgXHVkMmI5XHVjOWQ1IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWFjZTAsIFx1YmFhOFx1YjRlMCBcdWIyZjVcdWJjYzBcdWM3NDAgXHVjNjA4IFx1YjYxMFx1YjI5NCBcdWM1NDRcdWIyYzhcdWM2MjRcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZjVcdWJjYzBcdWM3NDQgXHViNGU0XHVjNzQwIFx1ZDZjNFx1YzVkMCBcdWIyZTRcdWM3NGMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWM4XHViYjM4XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCAxMDBcdWM2ZDBcdWM1MjkgXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHViYTM4XHViMmM4IFx1YzBhY1x1YzgxNVx1Yzc3NCBcdWIxMDlcdWIxMDlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzYzhcdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzgwMVx1YWM4YyBcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzljOFx1YmIzOFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwIFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWMxMzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYjNjXHVjY2I0XHVjNzU4IFx1ZDJiOVx1YzlkNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTU4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWI5N2MgXHVhZDZjXHViY2M0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmI5XHVjOWQ1XHVjNzU4IFx1YWMxY1x1YzIxOCBtXHVhY2ZjIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsdDsgbSAmbGU7IDExLCAwICZsdDsgbiAmbGU7IDEyOCkgXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJiM2NcdWNjYjRcdWM3NTggXHVkMmI5XHVjOWQ1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMmI5XHVjOWQ1XHVjNzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBtXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVhYzAxIFx1YWMxMlx1Yzc0MCAxKFx1YzYwOCkgXHViNjEwXHViMjk0IDAoXHVjNTQ0XHViMmM4XHVjNjI0KVx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWQyYjlcdWM5ZDVcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTU4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWJiM2NcdWNjYjRcdWI5N2MgXHVhZDZjXHViY2M0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1YzgwMVx1YWM4YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4ODIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUd2VudHkgUXVlc3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIGNsb3NlZCB3b3JsZCBhbmQgYSBzZXQgb2YgZmVhdHVyZXMgdGhhdCBhcmUgZGVmaW5lZCBmb3IgYWxsIHRoZSBvYmplY3RzIGluIHRoZSB3b3JsZC4gRWFjaCBmZWF0dXJlIGNhbiBiZSBhbnN3ZXJlZCB3aXRoICZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzsuIFVzaW5nIHRob3NlIGZlYXR1cmVzLCB3ZSBjYW4gaWRlbnRpZnkgYW55IG9iamVjdCBmcm9tIHRoZSByZXN0IG9mIHRoZSBvYmplY3RzIGluIHRoZSB3b3JsZC4gSW4gb3RoZXIgd29yZHMsIGVhY2ggb2JqZWN0IGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIGZpeGVkLWxlbmd0aCBzZXF1ZW5jZSBvZiBib29sZWFucy4gQW55IG9iamVjdCBpcyBkaVx1ZmIwMGVyZW50IGZyb20gb3RoZXIgb2JqZWN0cyBieSBhdCBsZWFzdCBvbmUgZmVhdHVyZS48XC9wPlxyXG5cclxuPHA+WW91IHdvdWxkIGxpa2UgdG8gaWRlbnRpZnkgYW4gb2JqZWN0IGZyb20gb3RoZXJzLiBGb3IgdGhpcyBwdXJwb3NlLCB5b3UgY2FuIGFzayBhIHNlcmllcyBvZiBxdWVzdGlvbnMgdG8gc29tZW9uZSB3aG8ga25vd3Mgd2hhdCB0aGUgb2JqZWN0IGlzLiBFdmVyeSBxdWVzdGlvbiB5b3UgY2FuIGFzayBpcyBhYm91dCBvbmUgb2YgdGhlIGZlYXR1cmVzLiBIZVwvc2hlIGltbWVkaWF0ZWx5IGFuc3dlcnMgZWFjaCBxdWVzdGlvbiB3aXRoICZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzsgY29ycmVjdGx5LiBZb3UgY2FuIGNob29zZSB0aGUgbmV4dCBxdWVzdGlvbiBhZnRlciB5b3UgZ2V0IHRoZSBhbnN3ZXIgdG8gdGhlIHByZXZpb3VzIHF1ZXN0aW9uLjxcL3A+XHJcblxyXG48cD5Zb3Uga2luZGx5IHBheSB0aGUgYW5zd2VyZXIgMTAwIHllbiBhcyBhIHRpcCBmb3IgZWFjaCBxdWVzdGlvbi4gQmVjYXVzZSB5b3UgZG9uJnJzcXVvO3QgaGF2ZSBzdXJwbHVzIG1vbmV5LCBpdCBpcyBuZWNlc3NhcnkgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBxdWVzdGlvbnMgaW4gdGhlIHdvcnN0IGNhc2UuIFlvdSBkb24mcnNxdW87dCBrbm93IHdoYXQgaXMgdGhlIGNvcnJlY3QgYW5zd2VyLCBidXQgZm9ydHVuYXRlbHkga25vdyBhbGwgdGhlIG9iamVjdHMgaW4gdGhlIHdvcmxkLiBUaGVyZWZvcmUsIHlvdSBjYW4gcGxhbiBhbiBvcHRpbWFsIHN0cmF0ZWd5IGJlZm9yZSB5b3Ugc3RhcnQgcXVlc3Rpb25pbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBtdWx0aXBsZSBkYXRhc2V0cy4gRWFjaCBkYXRhc2V0IGJlZ2lucyB3aXRoIGEgbGluZSB3aGljaCBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMsIG0gYW5kIG46IHRoZSBudW1iZXIgb2YgZmVhdHVyZXMsIGFuZCB0aGUgbnVtYmVyIG9mIG9iamVjdHMsIHJlc3BlY3RpdmVseS4gWW91IGNhbiBhc3N1bWUgMCAmbHQ7IG0gJmxlOyAxMSBhbmQgMCAmbHQ7IG4gJmxlOyAxMjguIEl0IGlzIGZvbGxvd2VkIGJ5IG4gbGluZXMsIGVhY2ggb2Ygd2hpY2ggY29ycmVzcG9uZHMgdG8gYW4gb2JqZWN0LiBFYWNoIGxpbmUgaW5jbHVkZXMgYSBiaW5hcnkgc3RyaW5nIG9mIGxlbmd0aCBtIHdoaWNoIHJlcHJlc2VudCB0aGUgdmFsdWUgKCZsZHF1bzt5ZXMmcmRxdW87IG9yICZsZHF1bztubyZyZHF1bzspIG9mIGZlYXR1cmVzLiBUaGVyZSBhcmUgbm8gdHdvIGlkZW50aWNhbCBvYmplY3RzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG1pbmltaXplIHRoZSBtYXhpbXVtIG51bWJlciBvZiBxdWVzdGlvbnMgYnkgd2hpY2ggZXZlcnkgb2JqZWN0IGlzIGlkZW50aWZpYWJsZSBhbmQgb3V0cHV0IHRoZSByZXN1bHQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2009 in Tokyo H번

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

© 2020 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호