시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1004 550 482 58.072%

문제

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가 있을 때, 두 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
W3sicHJvYmxlbV9pZCI6IjE5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEiLCJkZXNjcmlwdGlvbiI6IjxwPkROQVx1Yjc4MCBcdWM1YjRcdWI1YTQgXHVjNzIwXHVjODA0XHViYjNjXHVjOWM4XHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWJkODRcdWM3OTBcdWM3NzRcdWIyZTQuIFx1Yzc3NCBETkFcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCA0XHVhYzAwXHVjOWMwXHVjNzU4IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0KEFkZW5pbmUsIFRoeW1pbmUsIEd1YW5pbmUsIEN5dG9zaW5lKS4gXHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhNCBETkFcdWM3NTggXHViYjNjXHVjOWM4XHVjNzQ0IFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWI1NGMsIFx1Yzc3NCBETkFcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yzc1OCBcdWNjYWJcdWFlMDBcdWM3OTBcdWI5N2MgXHViNTMwXHVjMTFjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIFRoeW1pbmUtQWRlbmluZS1BZGVuaW5lLUN5dG9zaW5lLVRoeW1pbmUtR3VhbmluZS1DeXRvc2luZS1DeXRvc2luZS1HdWFuaW5lLUFkZW5pbmUtVGh5bWluZVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgRE5BXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQsICZsZHF1bztUQUFDVEdDQ0dBVCZyZHF1bztcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBIYW1taW5nIERpc3RhbmNlXHViNzgwIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViNDUwIEROQVx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWI0NTAgRE5BXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yjk3YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2RcdWM1ZDAgJmxkcXVvO0FHQ0FUJnF1b3Q7XHVjNjQwICZyZHF1bztHR0FBVCZxdW90O1x1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWMxMzggXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWIyZTRcdWI5NzRcdWJiYzBcdWI4NWMgSGFtbWluZyBEaXN0YW5jZVx1YjI5NCAyXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWFjMDAgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBuXHVhYzFjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgRE5BXHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjKFx1Yzc3NCBETkFcdWI5N2MgYTFhMmEzYTQuLi5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwKSBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEROQSBzXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgc1x1YzY0MCBhMVx1Yzc1OCBIYW1taW5nIERpc3RhbmNlICsgc1x1YzY0MCBhMlx1Yzc1OCBIYW1taW5nIERpc3RhbmNlICsgc1x1YzY0MCBhM1x1Yzc1OCBIYW1taW5nIERpc3RhbmNlIC4uLiBcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBETkFcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBOXHVhYzFjXHVjNzU4IEROQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMSwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWM3NDAgNTBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEROQSBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOCBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWRmOFx1YjdlY1x1ZDU1YyBETkFcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHViNTRjXHVjNWQwXHViMjk0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTk2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkROQSBDb25zZW5zdXMgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RuYWIxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM3MXB4OyB3aWR0aDoyNjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5ETkEgKERlb3h5cmlib251Y2xlaWMgQWNpZCkgaXMgdGhlIG1vbGVjdWxlIHdoaWNoIGNvbnRhaW5zIHRoZSBnZW5ldGljIGluc3RydWN0aW9ucy4gSXQgY29uc2lzdHMgb2YgZm91ciBkaWZmZXJlbnQgbnVjbGVvdGlkZXMsIG5hbWVseSBBZGVuaW5lLCBUaHltaW5lLCBHdWFuaW5lLCBhbmQgQ3l0b3NpbmUgYXMgc2hvd24gaW4gRmlndXJlIDEuIElmIHdlIHJlcHJlc2VudCBhIG51Y2xlb3RpZGUgYnkgaXRzIGluaXRpYWwgY2hhcmFjdGVyLCBhIEROQSBzdHJhbmQgY2FuIGJlIHJlZ2FyZGVkIGFzIGEgbG9uZyBzdHJpbmcgKHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMpIGNvbnNpc3Rpbmcgb2YgdGhlIGZvdXIgY2hhcmFjdGVycyBBLCBULCBHLCBhbmQgQy4gRm9yIGV4YW1wbGUsIGFzc3VtZSB3ZSBhcmUgZ2l2ZW4gc29tZSBwYXJ0IG9mIGEgRE5BIHN0cmFuZCB3aGljaCBpcyBjb21wb3NlZCBvZiB0aGUgZm9sbG93aW5nIHNlcXVlbmNlIG9mIG51Y2xlb3RpZGVzOiAmbGRxdW87VGh5bWluZS1BZGVuaW5lLUFkZW5pbmUtQ3l0b3NpbmUtVGh5bWluZS1HdWFuaW5lLUN5dG9zaW5lLUN5dG9zaW5lLUd1YW5pbmUtQWRlbmluZS1UaHltaW5lJnJkcXVvOyBUaGVuIHdlIGNhbiByZXByZXNlbnQgdGhlIGFib3ZlIEROQSBzdHJhbmQgd2l0aCB0aGUgc3RyaW5nICZsZHF1bztUQUFDVEdDQ0dBVC4mcmRxdW87PFwvcD5cclxuXHJcbjxwPlRoZSBiaW9sb2dpc3QgUHJvZi4gQWhuIGZvdW5kIHRoYXQgYSBnZW5lIFggY29tbW9ubHkgZXhpc3RzIGluIHRoZSBETkEgc3RyYW5kcyBvZiBmaXZlIGRpZmZlcmVudCBraW5kcyBvZiBhbmltYWxzLCBuYW1lbHkgZG9ncywgY2F0cywgaG9yc2VzLCBjb3dzLCBhbmQgbW9ua2V5cy4gSGUgYWxzbyBkaXNjb3ZlcmVkIHRoYXQgdGhlIEROQSBzZXF1ZW5jZXMgb2YgdGhlIGdlbmUgWCBmcm9tIGVhY2ggYW5pbWFsIHdlcmUgdmVyeSBhbGlrZS4gU2VlIEZpZ3VyZSAyLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RuYWIyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2OXB4OyB3aWR0aDozNjJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Qcm9mLiBBaG4gdGhvdWdodCB0aGF0IGh1bWFucyBtaWdodCBhbHNvIGhhdmUgdGhlIGdlbmUgWCBhbmQgZGVjaWRlZCB0byBzZWFyY2ggZm9yIHRoZSBETkEgc2VxdWVuY2Ugb2YgWCBpbiBodW1hbiBETkEuIEhvd2V2ZXIsIGJlZm9yZSBzZWFyY2hpbmcsIGhlIHNob3VsZCBkZWZpbmUgYSByZXByZXNlbnRhdGl2ZSBETkEgc2VxdWVuY2Ugb2YgZ2VuZSBYIGJlY2F1c2UgaXRzIHNlcXVlbmNlcyBhcmUgbm90IGV4YWN0bHkgdGhlIHNhbWUgaW4gdGhlIEROQSBvZiB0aGUgZml2ZSBhbmltYWxzLiBIZSBkZWNpZGVkIHRvIHVzZSB0aGUgSGFtbWluZyBkaXN0YW5jZSB0byBkZWZpbmUgdGhlIHJlcHJlc2VudGF0aXZlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgSGFtbWluZyBkaXN0YW5jZSBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjaGFyYWN0ZXJzIGF0IGVhY2ggcG9zaXRpb24gZnJvbSB0d28gc3RyaW5ncyBvZiBlcXVhbCBsZW5ndGguIEZvciBleGFtcGxlLCBhc3N1bWUgd2UgYXJlIGdpdmVuIHRoZSB0d28gc3RyaW5ncyAmbGRxdW87QUdDQVQmcmRxdW87IGFuZCAmbGRxdW87R0dBQVQuJnJkcXVvOyBUaGUgSGFtbWluZyBkaXN0YW5jZSBvZiB0aGVzZSB0d28gc3RyaW5ncyBpcyAyIGJlY2F1c2UgdGhlIDFzdCBhbmQgdGhlIDNyZCBjaGFyYWN0ZXJzIG9mIHRoZSB0d28gc3RyaW5ncyBhcmUgZGlmZmVyZW50LiBVc2luZyB0aGUgSGFtbWluZyBkaXN0YW5jZSwgd2UgY2FuIGRlZmluZSBhIHJlcHJlc2VudGF0aXZlIHN0cmluZyBmb3IgYSBzZXQgb2YgbXVsdGlwbGUgc3RyaW5ncyBvZiBlcXVhbCBsZW5ndGguIEdpdmVuIGEgc2V0IG9mIHN0cmluZ3Mge3MxLCAuLi4sIHNtfSBvZiBsZW5ndGggbiwgdGhlIGNvbnNlbnN1cyBlcnJvciBiZXR3ZWVuIGEgc3RyaW5nIHkgb2YgbGVuZ3RoIG4gYW5kIHRoZSBzZXQgUyBpcyB0aGUgc3VtIG9mIHRoZSBIYW1taW5nIGRpc3RhbmNlcyBiZXR3ZWVuIHkgYW5kIGVhY2ggc2kgaW4gUy4gSWYgdGhlIGNvbnNlbnN1cyBlcnJvciBiZXR3ZWVuIGlzIHkgYW5kIFMgaXMgdGhlIG1pbmltdW0gYW1vbmcgYWxsIHBvc3NpYmxlIHN0cmluZ3Mgb2YgbGVuZ3RoIG4sIGlzIGNhbGxlZCBhIGNvbnNlbnN1cyBzdHJpbmcgb2YgLiBGb3IgZXhhbXBsZSwgZ2l2ZW4gdGhlIHRocmVlIHN0cmluZ3MgJmxkcXVvO0FHQ0FUJnJkcXVvOywgJmxkcXVvO0FHQUNUJnJkcXVvOywgYW5kICZsZHF1bztHR0FBVCZyZHF1bzssIHRoZSBjb25zZW5zdXMgc3RyaW5nIG9mIHRoZSBnaXZlbiBzdHJpbmdzIGlzICZsZHF1bztBR0FBVCZyZHF1bzsgYmVjYXVzZSB0aGUgc3VtIG9mIHRoZSBIYW1taW5nIGRpc3RhbmNlcyBiZXR3ZWVuICZsZHF1bztBR0FBVCZyZHF1bzsgYW5kIHRoZSB0aHJlZSBzdHJpbmdzIGlzIDMgd2hpY2ggaXMgbWluaW1hbC4gKEluIHRoaXMgY2FzZSwgdGhlIGNvbnNlbnN1cyBzdHJpbmcgaXMgdW5pcXVlLCBidXQgaW4gZ2VuZXJhbCwgdGhlcmUgY2FuIGJlIG1vcmUgdGhhbiBvbmUgY29uc2Vuc3VzIHN0cmluZy4pIFdlIHVzZSB0aGUgY29uc2Vuc3VzIHN0cmluZyBhcyBhIHJlcHJlc2VudGF0aXZlIG9mIHRoZSBETkEgc2VxdWVuY2UuIEZvciB0aGUgZXhhbXBsZSBvZiBGaWd1cmUgMiBhYm92ZSwgYSBjb25zZW5zdXMgc3RyaW5nIG9mIGdlbmUgWCBpcyAmbGRxdW87R0NBQUFUR0dDVEdUR0NBJnJkcXVvOyBhbmQgdGhlIGNvbnNlbnN1cyBlcnJvciBpcyA3LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VycyBhbmQgd2hpY2ggYXJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGludGVnZXIgbSAoNCAmbGU7IG0gJmxlOyA1MCkgcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIEROQSBzZXF1ZW5jZXMgYW5kIG4oNCAmbGU7IG4gJmxlOyAxMDAwKSByZXByZXNlbnRzIHRoZSBsZW5ndGggb2YgdGhlIEROQSBzZXF1ZW5jZXMsIHJlc3BlY3RpdmVseS4gSW4gZWFjaCBvZiB0aGUgbmV4dCBtIGxpbmVzLCBlYWNoIEROQSBzZXF1ZW5jZSBpcyBnaXZlbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCB0aGUgY29uc2Vuc3VzIHN0cmluZyBpbiB0aGUgZmlyc3QgbGluZSBvZiBlYWNoIGNhc2UgYW5kIHRoZSBjb25zZW5zdXMgZXJyb3IgaW4gdGhlIHNlY29uZCBsaW5lIG9mIGVhY2ggY2FzZS4gSWYgdGhlcmUgZXhpc3RzIG1vcmUgdGhhbiBvbmUgY29uc2Vuc3VzIHN0cmluZywgcHJpbnQgdGhlIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXN0IGNvbnNlbnN1cyBzdHJpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgc2hvd3Mgc2FtcGxlIGlucHV0IGFuZCBvdXRwdXQgZm9yIHRocmVlIHRlc3QgY2FzZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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