시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB172978756.494%

문제

'인간 유전자 서열(Human Gene Function)'이란 인간의 유전 정보를 담고 있는 서열입니다. 이 유전자 서열은 DNA라는 분자에 표현되어 있는데, 아시다시피 DNA를 구성하는 염기는 아데닌, 구아닌, 티민, 사이토신의 네 개밖에 없기 때문에 인간 유전자 서열은 'A', 'G', 'T', 'C' 의 네 개의 문자로만 구성됩니다.

어떤 두 인간 유전자 서열이 주어질 때, 이 두 서열 간 유사도(비슷한 정도, similarity)를 측정하고 싶습니다. 이는 다음과 같은 대응표를 참조하여 아래와 같이 정의됩니다.

table.png

  • 각 서열의 곳곳에 적당히 공백('*')을 삽입하여 같은 길이의 문자열로 만든다. 그리고 위 표에 의해, 같은 위치에 있는 두 문자들의 매칭값에 해당하는 값들을 모두 더하면 어떤 값을 얻을 수 있다. (단, 공백 끼리 매칭하는 것은 불가능하기에 표의 값이 주어져있지 않다)
  • 공백을 여러 가지 방법으로 삽입할 수 있는데, 가능한 모든 방법 중 매칭값의 합이 가장 최대가 될 때, 그 값을 유사도라고 한다.

예를 들어, 두 서열이 각각 AGTGATG와 GTTAG 라고 합시다.

만약 공백을 아래와 같이 넣는다면 매칭값의 합은 다음과 같이 9가 됩니다.

AGTGAT*G
*GT**TAG
→  (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.

하지만, 만약 공백을 다음과 같이 넣는다면 매칭값은 14가 되고, 이것이 모든 가능한 방법 중 가장 큰 매칭값을 나타냅니다. 따라서 최종적으로 두 서열 간의 유사도는 14가 됩니다.

AGTGATG
*GTTA*G
→ (-3)+5+5+(-2)+5+(-1) +5=14

두 서열이 주어질 때, 유사도를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어집니다.

T개의 테스트 케이스마다 두 개의 줄로 구성된 입력이 주어집니다.

각 줄은 서열의 길이와, 인간 유전자 서열을 담고 있습니다.

(모든 인간 유전자 서열의 길이는 100을 넘지 않는다고 합니다)

출력

각 테스트 케이스 별로, 주어진 두 인간 유전자 서열의 유사도를 출력합니다.

예제 입력 1

2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA

예제 출력 1

14
21
W3sicHJvYmxlbV9pZCI6IjczNDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWM4MDRcdWM3OTAgXHVkNTY4XHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD4mIzM5O1x1Yzc3OFx1YWMwNCBcdWM3MjBcdWM4MDRcdWM3OTAgXHVjMTFjXHVjNWY0KEh1bWFuIEdlbmUgRnVuY3Rpb24pJiMzOTtcdWM3NzRcdWI3ODAgXHVjNzc4XHVhYzA0XHVjNzU4IFx1YzcyMFx1YzgwNCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMmY0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWM1ZjRcdWM3ODVcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWM3MjBcdWM4MDRcdWM3OTAgXHVjMTFjXHVjNWY0XHVjNzQwIEROQVx1Yjc3Y1x1YjI5NCBcdWJkODRcdWM3OTBcdWM1ZDAgXHVkNDVjXHVkNjA0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNTQ0XHVjMmRjXHViMmU0XHVjMmRjXHVkNTNjIEROQVx1Yjk3YyBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgXHVjNWZjXHVhZTMwXHViMjk0IFx1YzU0NFx1YjM3MFx1YjJjYywgXHVhZDZjXHVjNTQ0XHViMmNjLCBcdWQyZjBcdWJiZmMsIFx1YzBhY1x1Yzc3NFx1ZDFhMFx1YzJlMFx1Yzc1OCBcdWIxMjQgXHVhYzFjXHViYzE2XHVjNWQwIFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNzc4XHVhYzA0IFx1YzcyMFx1YzgwNFx1Yzc5MCBcdWMxMWNcdWM1ZjRcdWM3NDAmbmJzcDsmIzM5O0EmIzM5OywgJiMzOTtHJiMzOTssICYjMzk7VCYjMzk7LCAmIzM5O0MmIzM5OyBcdWM3NTggXHViMTI0IFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVhZDZjXHVjMTMxXHViNDI5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHViNDUwIFx1Yzc3OFx1YWMwNCBcdWM3MjBcdWM4MDRcdWM3OTAgXHVjMTFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1Yzc3NCBcdWI0NTAgXHVjMTFjXHVjNWY0IFx1YWMwNCBcdWM3MjBcdWMwYWNcdWIzYzQoXHViZTQ0XHVjMmI3XHVkNTVjIFx1YzgxNVx1YjNjNCwgc2ltaWxhcml0eSlcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTU4XHVhY2UwIFx1YzJmNlx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViMzAwXHVjNzUxXHVkNDVjXHViOTdjIFx1Y2MzOFx1Yzg3MFx1ZDU1OFx1YzVlYyBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJ0YWJsZS5wbmdcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8wMGU4YjYzYi0yZTVkLTQ5NmYtYmFiMC0zMWUyNGIyYWVhNjRcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWMwMSBcdWMxMWNcdWM1ZjRcdWM3NTggXHVhY2YzXHVhY2YzXHVjNWQwIFx1YzgwMVx1YjJmOVx1ZDc4OCBcdWFjZjVcdWJjMzEoJiMzOTsqJiMzOTspXHVjNzQ0IFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YzVlYyBcdWFjMTlcdWM3NDAgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3MDQgXHVkNDVjXHVjNWQwIFx1Yzc1OFx1ZDU3NCwgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWI5ZTRcdWNlNmRcdWFjMTJcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YWMxMlx1YjRlNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViMzU0XHVkNTU4XHViYTc0IFx1YzViNFx1YjVhNCBcdWFjMTJcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWIyZTgsIFx1YWNmNVx1YmMzMSBcdWIwN2NcdWI5YWMgXHViOWU0XHVjZTZkXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWFlMzBcdWM1ZDAgXHVkNDVjXHVjNzU4IFx1YWMxMlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4MzhcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0KTxcL2xpPlxyXG5cdDxsaT5cdWFjZjVcdWJjMzFcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMGJkXHVjNzg1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHViYzI5XHViYzk1IFx1YzkxMSBcdWI5ZTRcdWNlNmRcdWFjMTJcdWM3NTggXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDIwIFx1YjU0YywgXHVhZGY4IFx1YWMxMlx1Yzc0NCBcdWM3MjBcdWMwYWNcdWIzYzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjQ1MCBcdWMxMWNcdWM1ZjRcdWM3NzQgXHVhYzAxXHVhYzAxIEFHVEdBVEdcdWM2NDAgR1RUQUcgXHViNzdjXHVhY2UwIFx1ZDU2OVx1YzJkY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YjEyM1x1YjI5NFx1YjJlNFx1YmE3NCBcdWI5ZTRcdWNlNmRcdWFjMTJcdWM3NTggXHVkNTY5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgOVx1YWMwMCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFHVEdBVCpHXHJcbipHVCoqVEFHXHJcbiZyYXJyOyAgKC0zKSs1KzUrKC0yKSsoLTMpKzUrKC0zKSs1PTkuPFwvcHJlPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWI5Y2NcdWM1N2QgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMTIzXHViMjk0XHViMmU0XHViYTc0IFx1YjllNFx1Y2U2ZFx1YWMxMlx1Yzc0MCAxNFx1YWMwMCBcdWI0MThcdWFjZTAsIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWJhYThcdWI0ZTAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NSBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWI5ZTRcdWNlNmRcdWFjMTJcdWM3NDQgXHViMDk4XHVkMGMwXHViMGM1XHViMmM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjIFx1YjQ1MCBcdWMxMWNcdWM1ZjQgXHVhYzA0XHVjNzU4IFx1YzcyMFx1YzBhY1x1YjNjNFx1YjI5NCAxNFx1YWMwMCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFHVEdBVEdcclxuKkdUVEEqR1xyXG4mcmFycjsgKC0zKSs1KzUrKC0yKSs1KygtMSkgKzU9MTQ8XC9wcmU+XHJcblxyXG48cD5cdWI0NTAgXHVjMTFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YzcyMFx1YzBhY1x1YjNjNFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWMxMWNcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwLCBcdWM3NzhcdWFjMDQgXHVjNzIwXHVjODA0XHVjNzkwIFx1YzExY1x1YzVmNFx1Yzc0NCBcdWIyZjRcdWFjZTAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD4oXHViYWE4XHViNGUwIFx1Yzc3OFx1YWMwNCBcdWM3MjBcdWM4MDRcdWM3OTAmbmJzcDtcdWMxMWNcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHVhY2UwIFx1ZDU2OVx1YjJjOFx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjYzRcdWI4NWMsIFx1YzhmY1x1YzViNFx1YzljNCBcdWI0NTAgXHVjNzc4XHVhYzA0IFx1YzcyMFx1YzgwNFx1Yzc5MCBcdWMxMWNcdWM1ZjRcdWM3NTggXHVjNzIwXHVjMGFjXHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3MzQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSHVtYW4gR2VuZSBGdW5jdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkl0IGlzIHdlbGwga25vd24gdGhhdCBhIGh1bWFuIGdlbmUgY2FuIGJlIGNvbnNpZGVyZWQgYXMgYSBzZXF1ZW5jZSwgY29uc2lzdGluZyBvZiBmb3VyIG51Y2xlb3RpZGVzLCB3aGljaCBhcmUgc2ltcGx5IGRlbm90ZWQgYnkgZm91ciBsZXR0ZXJzLCBBLCBDLCBHLCBhbmQgVC4gQmlvbG9naXN0cyBoYXZlIGJlZW4gaW50ZXJlc3RlZCBpbiBpZGVudGlmeWluZyBodW1hbiBnZW5lcyBhbmQgZGV0ZXJtaW5pbmcgdGhlaXIgZnVuY3Rpb25zLCBiZWNhdXNlIHRoZXNlIGNhbiBiZSB1c2VkIHRvIGRpYWdub3NlIGh1bWFuIGRpc2Vhc2VzIGFuZCB0byBkZXNpZ24gbmV3IGRydWdzIGZvciB0aGVtLjxcL3A+XHJcblxyXG48cD5BIGh1bWFuIGdlbmUgY2FuIGJlIGlkZW50aWZpZWQgdGhyb3VnaCBhIHNlcmllcyBvZiB0aW1lLWNvbnN1bWluZyBiaW9sb2dpY2FsIGV4cGVyaW1lbnRzLCBvZnRlbiB3aXRoIHRoZSBoZWxwIG9mIGNvbXB1dGVyIHByb2dyYW1zLiBPbmNlIGEgc2VxdWVuY2Ugb2YgYSBnZW5lIGlzIG9idGFpbmVkLCB0aGUgbmV4dCBqb2IgaXMgdG8gZGV0ZXJtaW5lIGl0cyBmdW5jdGlvbi4gT25lIG9mIHRoZSBtZXRob2RzIGZvciBiaW9sb2dpc3RzIHRvIHVzZSBpbiBkZXRlcm1pbmluZyB0aGUgZnVuY3Rpb24gb2YgYSBuZXcgZ2VuZSBzZXF1ZW5jZSB0aGF0IHRoZXkgaGF2ZSBqdXN0IGlkZW50aWZpZWQgaXMgdG8gc2VhcmNoIGEgZGF0YWJhc2Ugd2l0aCB0aGUgbmV3IGdlbmUgYXMgYSBxdWVyeS4gVGhlIGRhdGFiYXNlIHRvIGJlIHNlYXJjaGVkIHN0b3JlcyBtYW55IGdlbmUgc2VxdWVuY2VzIGFuZCB0aGVpciBmdW5jdGlvbnMgJm5kYXNoOyBtYW55IHJlc2VhcmNoZXJzIGhhdmUgYmVlbiBzdWJtaXR0aW5nIHRoZWlyIGdlbmVzIGFuZCBmdW5jdGlvbnMgdG8gdGhlIGRhdGFiYXNlIGFuZCB0aGUgZGF0YWJhc2UgaXMgZnJlZWx5IGFjY2Vzc2libGUgdGhyb3VnaCB0aGUgSW50ZXJuZXQuPFwvcD5cclxuXHJcbjxwPkEgZGF0YWJhc2Ugc2VhcmNoIHdpbGwgcmV0dXJuIGEgbGlzdCBvZiBnZW5lIHNlcXVlbmNlcyBmcm9tIHRoZSBkYXRhYmFzZSB0aGF0IGFyZSBzaW1pbGFyIHRvIHRoZSBxdWVyeSBnZW5lLiBCaW9sb2dpc3RzIGFzc3VtZSB0aGF0IHNlcXVlbmNlIHNpbWlsYXJpdHkgb2Z0ZW4gaW1wbGllcyBmdW5jdGlvbmFsIHNpbWlsYXJpdHkuIFNvLCB0aGUgZnVuY3Rpb24gb2YgdGhlIG5ldyBnZW5lIG1pZ2h0IGJlIG9uZSBvZiB0aGUgZnVuY3Rpb25zIHRoYXQgdGhlIGdlbmVzIGZyb20gdGhlIGxpc3QgaGF2ZS4gVG8gZXhhY3RseSBkZXRlcm1pbmUgd2hpY2ggb25lIGlzIHRoZSByaWdodCBvbmUgYW5vdGhlciBzZXJpZXMgb2YgYmlvbG9naWNhbCBleHBlcmltZW50cyB3aWxsIGJlIG5lZWRlZC48XC9wPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gbWFrZSBhIHByb2dyYW0gdGhhdCBjb21wYXJlcyB0d28gZ2VuZXMgYW5kIGRldGVybWluZXMgdGhlaXIgc2ltaWxhcml0eSBhcyBleHBsYWluZWQgYmVsb3cuIFlvdXIgcHJvZ3JhbSBtYXkgYmUgdXNlZCBhcyBhIHBhcnQgb2YgdGhlIGRhdGFiYXNlIHNlYXJjaCBpZiB5b3UgY2FuIHByb3ZpZGUgYW4gZWZmaWNpZW50IG9uZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdHdvIGdlbmVzIEFHVEdBVEcgYW5kIEdUVEFHLCBob3cgc2ltaWxhciBhcmUgdGhleT8gT25lIG9mIHRoZSBtZXRob2RzIHRvIG1lYXN1cmUgdGhlIHNpbWlsYXJpdHkgb2YgdHdvIGdlbmVzIGlzIGNhbGxlZCBhbGlnbm1lbnQuIEluIGFuIGFsaWdubWVudCwgc3BhY2VzIGFyZSBpbnNlcnRlZCwgaWYgbmVjZXNzYXJ5LCBpbiBhcHByb3ByaWF0ZSBwb3NpdGlvbnMgb2YgdGhlIGdlbmVzIHRvIG1ha2UgdGhlbSBlcXVhbGx5IGxvbmcgYW5kIHNjb3JlIHRoZSByZXN1bHRpbmcgZ2VuZXMgYWNjb3JkaW5nIHRvIGEgc2NvcmluZyBtYXRyaXguPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBvbmUgc3BhY2UgaXMgaW5zZXJ0ZWQgaW50byBBR1RHQVRHIHRvIHJlc3VsdCBpbiBBR1RHQVQtRywgYW5kIHRocmVlIHNwYWNlcyBhcmUgaW5zZXJ0ZWQgaW50byBHVFRBRyB0byByZXN1bHQgaW4gJm5kYXNoO0dULS1UQUcuIEEgc3BhY2UgaXMgZGVub3RlZCBieSBhIG1pbnVzIHNpZ24gKC0pLiBUaGUgdHdvIGdlbmVzIGFyZSBub3cgb2YgZXF1YWwgbGVuZ3RoLiBUaGVzZSB0d28gc3RyaW5ncyBhcmUgYWxpZ25lZDo8XC9wPlxyXG5cclxuPHByZT5cclxuQUdUR0FULUdcclxuLUdULS1UQUdcclxuPFwvcHJlPlxyXG5cclxuPHA+SW4gdGhpcyBhbGlnbm1lbnQsIHRoZXJlIGFyZSBmb3VyIG1hdGNoZXMsIG5hbWVseSwgRyBpbiB0aGUgc2Vjb25kIHBvc2l0aW9uLCBUIGluIHRoZSB0aGlyZCwgVCBpbiB0aGUgc2l4dGgsIGFuZCBHIGluIHRoZSBlaWdodGguIEVhY2ggcGFpciBvZiBhbGlnbmVkIGNoYXJhY3RlcnMgaXMgYXNzaWduZWQgYSBzY29yZSBhY2NvcmRpbmcgdG8gdGhlIGZvbGxvd2luZyBzY29yaW5nIG1hdHJpeC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjIwJVwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPiZuYnNwOzxcL3RkPlxyXG5cdFx0XHQ8dGg+QTxcL3RoPlxyXG5cdFx0XHQ8dGg+QzxcL3RoPlxyXG5cdFx0XHQ8dGg+RzxcL3RoPlxyXG5cdFx0XHQ8dGg+VDxcL3RoPlxyXG5cdFx0XHQ8dGg+LTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5BPFwvdGg+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD4tMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTI8XC90ZD5cclxuXHRcdFx0PHRkPi0xPFwvdGQ+XHJcblx0XHRcdDx0ZD4tMzxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5DPFwvdGg+XHJcblx0XHRcdDx0ZD4tMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTM8XC90ZD5cclxuXHRcdFx0PHRkPi0yPFwvdGQ+XHJcblx0XHRcdDx0ZD4tNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5HPFwvdGg+XHJcblx0XHRcdDx0ZD4tMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTM8XC90ZD5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPi0yPFwvdGQ+XHJcblx0XHRcdDx0ZD4tMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5UPFwvdGg+XHJcblx0XHRcdDx0ZD4tMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTI8XC90ZD5cclxuXHRcdFx0PHRkPi0yPFwvdGQ+XHJcblx0XHRcdDx0ZD41PFwvdGQ+XHJcblx0XHRcdDx0ZD4tMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4tPFwvdGg+XHJcblx0XHRcdDx0ZD4tMzxcL3RkPlxyXG5cdFx0XHQ8dGQ+LTQ8XC90ZD5cclxuXHRcdFx0PHRkPi0yPFwvdGQ+XHJcblx0XHRcdDx0ZD4tMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+KjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+KiBkZW5vdGVzIHRoYXQgYSBzcGFjZS1zcGFjZSBtYXRjaCBpcyBub3QgYWxsb3dlZC4gVGhlIHNjb3JlIG9mIHRoZSBhbGlnbm1lbnQgYWJvdmUgaXMgKC0zKSs1KzUrKC0yKSsoLTMpKzUrKC0zKSs1PTkuPFwvcD5cclxuXHJcbjxwPk9mIGNvdXJzZSwgbWFueSBvdGhlciBhbGlnbm1lbnRzIGFyZSBwb3NzaWJsZS4gT25lIGlzIHNob3duIGJlbG93IChhIGRpZmZlcmVudCBudW1iZXIgb2Ygc3BhY2VzIGFyZSBpbnNlcnRlZCBpbnRvIGRpZmZlcmVudCBwb3NpdGlvbnMpOjxcL3A+XHJcblxyXG48cHJlPlxyXG5BR1RHQVRHXHJcbiZuZGFzaDtHVFRBLUc8XC9wcmU+XHJcblxyXG48cD5UaGlzIGFsaWdubWVudCBnaXZlcyBhIHNjb3JlIG9mICgtMykrNSs1KygtMikrNSsoLTEpICs1PTE0LiBTbywgdGhpcyBvbmUgaXMgYmV0dGVyIHRoYW4gdGhlIHByZXZpb3VzIG9uZS4gQXMgYSBtYXR0ZXIgb2YgZmFjdCwgdGhpcyBvbmUgaXMgb3B0aW1hbCBzaW5jZSBubyBvdGhlciBhbGlnbm1lbnQgY2FuIGhhdmUgYSBoaWdoZXIgc2NvcmUuIFNvLCBpdCBpcyBzYWlkIHRoYXQgdGhlIHNpbWlsYXJpdHkgb2YgdGhlIHR3byBnZW5lcyBpcyAxNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoVCkgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lczogZWFjaCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIsIHRoZSBsZW5ndGggb2YgYSBnZW5lLCBmb2xsb3dlZCBieSBhIGdlbmUgc2VxdWVuY2UuIFRoZSBsZW5ndGggb2YgZWFjaCBnZW5lIHNlcXVlbmNlIGlzIGF0IGxlYXN0IG9uZSBhbmQgZG9lcyBub3QgZXhjZWVkIDEwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBwcmludCB0aGUgc2ltaWxhcml0eSBvZiBlYWNoIHRlc3QgY2FzZSwgb25lIHBlciBsaW5lLjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2001 D번

Contest > CTU FEE Local Contest > CTU FEE 2004 D번