시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1903 1043 921 59.152%

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. n개의 길이가 같은 DNA가 주어져 있을 때(이 DNA를 a1a2a3a4...이라고 하자) Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 a1의 Hamming Distance + s와 a2의 Hamming Distance + s와 a3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력 1

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제 출력 1

TAAGATAC
7

예제 입력 2

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

예제 출력 2

ACGTACGTAA
6

예제 입력 3

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

예제 출력 3

AAGTTACCAA
12
W3sicHJvYmxlbV9pZCI6IjE5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEiLCJkZXNjcmlwdGlvbiI6IjxwPkROQVx1Yjc4MCBcdWM1YjRcdWI1YTQgXHVjNzIwXHVjODA0XHViYjNjXHVjOWM4XHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWJkODRcdWM3OTBcdWM3NzRcdWIyZTQuIFx1Yzc3NCBETkFcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCA0XHVhYzAwXHVjOWMwXHVjNzU4IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0KEFkZW5pbmUsIFRoeW1pbmUsIEd1YW5pbmUsIEN5dG9zaW5lKS4gXHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhNCBETkFcdWM3NTggXHViYjNjXHVjOWM4XHVjNzQ0IFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWI1NGMsIFx1Yzc3NCBETkFcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yzc1OCBcdWNjYWJcdWFlMDBcdWM3OTBcdWI5N2MgXHViNTMwXHVjMTFjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIFRoeW1pbmUtQWRlbmluZS1BZGVuaW5lLUN5dG9zaW5lLVRoeW1pbmUtR3VhbmluZS1DeXRvc2luZS1DeXRvc2luZS1HdWFuaW5lLUFkZW5pbmUtVGh5bWluZVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgRE5BXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQsICZsZHF1bztUQUFDVEdDQ0dBVCZyZHF1bztcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBIYW1taW5nIERpc3RhbmNlXHViNzgwIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViNDUwIEROQVx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YjI3NFx1ZDA3NFx1YzYyNFx1ZDJmMFx1YjRkYyBcdWJiMzhcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZFx1YzVkMCAmbGRxdW87QUdDQVQmcXVvdDtcdWM2NDAgJnJkcXVvO0dHQUFUJnF1b3Q7XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVjNjQwIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YmJjMFx1Yjg1YyBIYW1taW5nIERpc3RhbmNlXHViMjk0IDJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuIG5cdWFjMWNcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMxOVx1Yzc0MCBETkFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMoXHVjNzc0IEROQVx1Yjk3YyBhMWEyYTNhNC4uLlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTApIEhhbW1pbmcgRGlzdGFuY2VcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgRE5BIHNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBzXHVjNjQwIGExXHVjNzU4IEhhbW1pbmcgRGlzdGFuY2UgKyBzXHVjNjQwIGEyXHVjNzU4IEhhbW1pbmcgRGlzdGFuY2UgKyBzXHVjNjQwIGEzXHVjNzU4IEhhbW1pbmcgRGlzdGFuY2UgLi4uIFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIEROQVx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIE5cdWFjMWNcdWM3NTggRE5BXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCAxLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YWNlMCwgTVx1Yzc0MCA1MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEhhbW1pbmcgRGlzdGFuY2VcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgRE5BIFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZGY4IEhhbW1pbmcgRGlzdGFuY2VcdWM3NTggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVhZGY4XHViN2VjXHVkNTVjIEROQVx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTY5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRE5BIENvbnNlbnN1cyBTdHJpbmciLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG5hYjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzcxcHg7IHdpZHRoOjI2OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkROQSAoRGVveHlyaWJvbnVjbGVpYyBBY2lkKSBpcyB0aGUgbW9sZWN1bGUgd2hpY2ggY29udGFpbnMgdGhlIGdlbmV0aWMgaW5zdHJ1Y3Rpb25zLiBJdCBjb25zaXN0cyBvZiBmb3VyIGRpZmZlcmVudCBudWNsZW90aWRlcywgbmFtZWx5IEFkZW5pbmUsIFRoeW1pbmUsIEd1YW5pbmUsIGFuZCBDeXRvc2luZSBhcyBzaG93biBpbiBGaWd1cmUgMS4gSWYgd2UgcmVwcmVzZW50IGEgbnVjbGVvdGlkZSBieSBpdHMgaW5pdGlhbCBjaGFyYWN0ZXIsIGEgRE5BIHN0cmFuZCBjYW4gYmUgcmVnYXJkZWQgYXMgYSBsb25nIHN0cmluZyAoc2VxdWVuY2Ugb2YgY2hhcmFjdGVycykgY29uc2lzdGluZyBvZiB0aGUgZm91ciBjaGFyYWN0ZXJzIEEsIFQsIEcsIGFuZCBDLiBGb3IgZXhhbXBsZSwgYXNzdW1lIHdlIGFyZSBnaXZlbiBzb21lIHBhcnQgb2YgYSBETkEgc3RyYW5kIHdoaWNoIGlzIGNvbXBvc2VkIG9mIHRoZSBmb2xsb3dpbmcgc2VxdWVuY2Ugb2YgbnVjbGVvdGlkZXM6ICZsZHF1bztUaHltaW5lLUFkZW5pbmUtQWRlbmluZS1DeXRvc2luZS1UaHltaW5lLUd1YW5pbmUtQ3l0b3NpbmUtQ3l0b3NpbmUtR3VhbmluZS1BZGVuaW5lLVRoeW1pbmUmcmRxdW87IFRoZW4gd2UgY2FuIHJlcHJlc2VudCB0aGUgYWJvdmUgRE5BIHN0cmFuZCB3aXRoIHRoZSBzdHJpbmcgJmxkcXVvO1RBQUNUR0NDR0FULiZyZHF1bzs8XC9wPlxyXG5cclxuPHA+VGhlIGJpb2xvZ2lzdCBQcm9mLiBBaG4gZm91bmQgdGhhdCBhIGdlbmUgWCBjb21tb25seSBleGlzdHMgaW4gdGhlIEROQSBzdHJhbmRzIG9mIGZpdmUgZGlmZmVyZW50IGtpbmRzIG9mIGFuaW1hbHMsIG5hbWVseSBkb2dzLCBjYXRzLCBob3JzZXMsIGNvd3MsIGFuZCBtb25rZXlzLiBIZSBhbHNvIGRpc2NvdmVyZWQgdGhhdCB0aGUgRE5BIHNlcXVlbmNlcyBvZiB0aGUgZ2VuZSBYIGZyb20gZWFjaCBhbmltYWwgd2VyZSB2ZXJ5IGFsaWtlLiBTZWUgRmlndXJlIDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG5hYjIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTY5cHg7IHdpZHRoOjM2MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlByb2YuIEFobiB0aG91Z2h0IHRoYXQgaHVtYW5zIG1pZ2h0IGFsc28gaGF2ZSB0aGUgZ2VuZSBYIGFuZCBkZWNpZGVkIHRvIHNlYXJjaCBmb3IgdGhlIEROQSBzZXF1ZW5jZSBvZiBYIGluIGh1bWFuIEROQS4gSG93ZXZlciwgYmVmb3JlIHNlYXJjaGluZywgaGUgc2hvdWxkIGRlZmluZSBhIHJlcHJlc2VudGF0aXZlIEROQSBzZXF1ZW5jZSBvZiBnZW5lIFggYmVjYXVzZSBpdHMgc2VxdWVuY2VzIGFyZSBub3QgZXhhY3RseSB0aGUgc2FtZSBpbiB0aGUgRE5BIG9mIHRoZSBmaXZlIGFuaW1hbHMuIEhlIGRlY2lkZWQgdG8gdXNlIHRoZSBIYW1taW5nIGRpc3RhbmNlIHRvIGRlZmluZSB0aGUgcmVwcmVzZW50YXRpdmUgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPlRoZSBIYW1taW5nIGRpc3RhbmNlIGlzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGNoYXJhY3RlcnMgYXQgZWFjaCBwb3NpdGlvbiBmcm9tIHR3byBzdHJpbmdzIG9mIGVxdWFsIGxlbmd0aC4gRm9yIGV4YW1wbGUsIGFzc3VtZSB3ZSBhcmUgZ2l2ZW4gdGhlIHR3byBzdHJpbmdzICZsZHF1bztBR0NBVCZyZHF1bzsgYW5kICZsZHF1bztHR0FBVC4mcmRxdW87IFRoZSBIYW1taW5nIGRpc3RhbmNlIG9mIHRoZXNlIHR3byBzdHJpbmdzIGlzIDIgYmVjYXVzZSB0aGUgMXN0IGFuZCB0aGUgM3JkIGNoYXJhY3RlcnMgb2YgdGhlIHR3byBzdHJpbmdzIGFyZSBkaWZmZXJlbnQuIFVzaW5nIHRoZSBIYW1taW5nIGRpc3RhbmNlLCB3ZSBjYW4gZGVmaW5lIGEgcmVwcmVzZW50YXRpdmUgc3RyaW5nIGZvciBhIHNldCBvZiBtdWx0aXBsZSBzdHJpbmdzIG9mIGVxdWFsIGxlbmd0aC4gR2l2ZW4gYSBzZXQgb2Ygc3RyaW5ncyB7czEsIC4uLiwgc219IG9mIGxlbmd0aCBuLCB0aGUgY29uc2Vuc3VzIGVycm9yIGJldHdlZW4gYSBzdHJpbmcgeSBvZiBsZW5ndGggbiBhbmQgdGhlIHNldCBTIGlzIHRoZSBzdW0gb2YgdGhlIEhhbW1pbmcgZGlzdGFuY2VzIGJldHdlZW4geSBhbmQgZWFjaCBzaSBpbiBTLiBJZiB0aGUgY29uc2Vuc3VzIGVycm9yIGJldHdlZW4gaXMgeSBhbmQgUyBpcyB0aGUgbWluaW11bSBhbW9uZyBhbGwgcG9zc2libGUgc3RyaW5ncyBvZiBsZW5ndGggbiwgaXMgY2FsbGVkIGEgY29uc2Vuc3VzIHN0cmluZyBvZiAuIEZvciBleGFtcGxlLCBnaXZlbiB0aGUgdGhyZWUgc3RyaW5ncyAmbGRxdW87QUdDQVQmcmRxdW87LCAmbGRxdW87QUdBQ1QmcmRxdW87LCBhbmQgJmxkcXVvO0dHQUFUJnJkcXVvOywgdGhlIGNvbnNlbnN1cyBzdHJpbmcgb2YgdGhlIGdpdmVuIHN0cmluZ3MgaXMgJmxkcXVvO0FHQUFUJnJkcXVvOyBiZWNhdXNlIHRoZSBzdW0gb2YgdGhlIEhhbW1pbmcgZGlzdGFuY2VzIGJldHdlZW4gJmxkcXVvO0FHQUFUJnJkcXVvOyBhbmQgdGhlIHRocmVlIHN0cmluZ3MgaXMgMyB3aGljaCBpcyBtaW5pbWFsLiAoSW4gdGhpcyBjYXNlLCB0aGUgY29uc2Vuc3VzIHN0cmluZyBpcyB1bmlxdWUsIGJ1dCBpbiBnZW5lcmFsLCB0aGVyZSBjYW4gYmUgbW9yZSB0aGFuIG9uZSBjb25zZW5zdXMgc3RyaW5nLikgV2UgdXNlIHRoZSBjb25zZW5zdXMgc3RyaW5nIGFzIGEgcmVwcmVzZW50YXRpdmUgb2YgdGhlIEROQSBzZXF1ZW5jZS4gRm9yIHRoZSBleGFtcGxlIG9mIEZpZ3VyZSAyIGFib3ZlLCBhIGNvbnNlbnN1cyBzdHJpbmcgb2YgZ2VuZSBYIGlzICZsZHF1bztHQ0FBQVRHR0NUR1RHQ0EmcmRxdW87IGFuZCB0aGUgY29uc2Vuc3VzIGVycm9yIGlzIDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGFuZCB3aGljaCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgaW50ZWdlciBtICg0ICZsZTsgbSAmbGU7IDUwKSByZXByZXNlbnRzIHRoZSBudW1iZXIgb2YgRE5BIHNlcXVlbmNlcyBhbmQgbig0ICZsZTsgbiAmbGU7IDEwMDApIHJlcHJlc2VudHMgdGhlIGxlbmd0aCBvZiB0aGUgRE5BIHNlcXVlbmNlcywgcmVzcGVjdGl2ZWx5LiBJbiBlYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMsIGVhY2ggRE5BIHNlcXVlbmNlIGlzIGdpdmVuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IHRoZSBjb25zZW5zdXMgc3RyaW5nIGluIHRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggY2FzZSBhbmQgdGhlIGNvbnNlbnN1cyBlcnJvciBpbiB0aGUgc2Vjb25kIGxpbmUgb2YgZWFjaCBjYXNlLiBJZiB0aGVyZSBleGlzdHMgbW9yZSB0aGFuIG9uZSBjb25zZW5zdXMgc3RyaW5nLCBwcmludCB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QgY29uc2Vuc3VzIHN0cmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBzaG93cyBzYW1wbGUgaW5wdXQgYW5kIG91dHB1dCBmb3IgdGhyZWUgdGVzdCBjYXNlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2006 B번

  • 빠진 조건을 찾은 사람: jsa3824
  • 잘못된 번역을 찾은 사람: previc1
  • 잘못된 데이터를 찾은 사람: tncks0121