문제
어떤 문자열 X의 확장이란 그 문자열의 어떤 위치 또는 가장 앞과 뒤에 공백을 임의의 개수(0, 1또는 그 이상)만큼 추가하는 것이다. 예를 들어, 문자열 X가 'abcbcd'일 때, 'abcb-cd', '-a-bcbcd-', 'abcd-cd-'는 문자열 X의 확장이 된다. (공백은 '-'로 표시)
A1을 문자열 A의 확장이라고 하고, B1을 문자열 B의 확장이라고 했을 때, A1과 B1의 길이가 같다면, 두 문자열의 거리를 정의할 수 있다. 두 문자열의 거리란, 같은 위치에서 문자의 거리의 합이다. 문자의 거리란, ASCII 코드 값의 차이를 말한다. 이때, 공백과 다른 문자와의 차이는 입력으로 주어지는 K이다.
두 문자열 A와 B가 주어졌을 때, 가장 짧은 거리를 갖는 A1과 B1을 찾는 프로그램을 작성하시오.
W3sicHJvYmxlbV9pZCI6IjMyNjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVkNjU1XHVjN2E1XHVhY2ZjIFx1YWM3MFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YmIzOFx1Yzc5MFx1YzVmNCBYXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc4MCBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM3MDRcdWNlNTggXHViNjEwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NWVcdWFjZmMgXHViNGE0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWM3ODRcdWM3NThcdWM3NTggXHVhYzFjXHVjMjE4KDAsIDFcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMSlcdWI5Y2NcdWQwN2MgXHVjZDk0XHVhYzAwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYjM4XHVjNzkwXHVjNWY0IFhcdWFjMDAgJiMzOTthYmNiY2QmIzM5O1x1Yzc3YyBcdWI1NGMsICYjMzk7YWJjYi1jZCYjMzk7LCAmIzM5Oy1hLWJjYmNkLSYjMzk7LCAmIzM5O2FiY2QtY2QtJiMzOTtcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFhcdWM3NTggXHVkNjU1XHVjN2E1XHVjNzc0IFx1YjQxY1x1YjJlNC4gKFx1YWNmNVx1YmMzMVx1Yzc0MCAmIzM5Oy0mIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGMpPFwvcD5cclxuXHJcbjxwPlxyXG5cdEExXHVjNzQ0IFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIEIxXHVjNzQ0IFx1YmIzOFx1Yzc5MFx1YzVmNCBCXHVjNzU4IFx1ZDY1NVx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBBMVx1YWNmYyBCMVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzE5XHViMmU0XHViYTc0LCBcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3ODAsIFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NzRcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI3ODAsIEFTQ0lJIFx1Y2Y1NFx1YjRkYyBcdWFjMTJcdWM3NTggXHVjYzI4XHVjNzc0XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjZjVcdWJjMzFcdWFjZmMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzY0MFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBLXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHViYjM4XHVjNzkwXHVjNWY0IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjMTZcdWIyOTQgQTFcdWFjZmMgQjFcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgMjAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1YWNmYyBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHVjNjQwXHVjNzU4IFx1YWM3MFx1YjlhYyBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBLICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMyNjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCbGFzdCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIGdpdmVuIHR3byBzdHJpbmdzLCBBIGFuZCBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbiBleHBhbnNpb24gb2Ygc29tZSBzdHJpbmcgWCBpcyBhIHN0cmluZyBjcmVhdGVkIGJ5IGFkZGluZyBvciBpbnNlcnRpbmcgYW55IG51bWJlciAoemVybywgb25lIG9yIG1vcmUpIG9mIGJsYW5rcyBhbnl3aGVyZSBpbiB0aGUgc3RyaW5nLCBvciBpbiB0aGUgYmVnZ2luaW5nIG9yIHRoZSBlbmQgb2YgdGhlIHN0cmluZy4gRWcuLCBpZiB0aGUgc3RyaW5nIFggaXMgJmxzcXVvO2FiY2JjZCZyc3F1bzssIHRoZW4gdGhlIHN0cmluZ3MgJiMzOTthYmNiLWNkJiMzOTssICYjMzk7LWEtYmNiY2QtJiMzOTsgYW5kICYjMzk7YWJjYi1jZC0mIzM5OyBhcmUgZXhwYW5zaW9ucyBvZiB0aGUgc3RyaW5nIFggKGJsYW5rcyBhcmUgZGVub3RlZCBieSB0aGUgY2hhcmFjdGVyICZsc3F1bzstJmxzcXVvOykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIEExIGlzIGFuIGV4cGFuc2lvbiBvZiB0aGUgc3RyaW5nIEEsIGFuZCBCMSBpcyBhbmQgZXhwYW5zaW9uIG9mIHRoZSBzdHJpbmcgQiwgYW5kIGlmIEExIGFuZCBCMSBhcmUgb2YgdGhlIHNhbWUgbGVuZ3RoLCB0aGVuIHdlIGRlZmluZSB0aGUgZGlzdGFuY2Ugb2YgdGhlIHN0cmluZ3MgQTEgYW5kIEIxIGFzIHRoZSBzdW0gb2YgdGhlIGRpc3RhbmNlcyBvZiB0aGUgY2hhcmFjdGVycyBvbiB0aGUgc2FtZSBwb3NpdGlvbnMgaW4gdGhlc2Ugc3RyaW5ncy4gV2UgZGVmaW5lIHRoZSBkaXN0YW5jZSBvZiB0d28gY2hhcmFjdGVycyBhcyB0aGUgYWJzb2x1dGUgZGlmZmVyZW5jZSBvZiB0aGVpciBBU0NJSSBjb2RlcywgZXhjZXB0IHRoZSBkaXN0YW5jZSBvZiB0aGUgYmxhbmsgYW5kIGFub3RoZXIgY2hhcmFjdGVyLCB3aGljaCBpcyBnaXZlbiAoYW5kIGVxdWFsIGZvciBhbGwgY2hhcmFjdGVycykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGZpbmRzIHRoZSBleHBhbnNpb25zIEExIGFuZCBCMSBvZiBzdHJpbmdzIEEgYW5kIEIsIHRoYXQgaGF2ZSB0aGUgc21hbGxlc3QgZGlmZmVyZW5jZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlIGNvbnNpc3RzIG9mIHRoZSBzdHJpbmcgQSwgYW5kIHRoZSBzZWNvbmQgbGluZSBvZiBzdHJpbmcgQi4gVGhleSBhcmUgY29uc2lzdGVkIG9ubHkgb2YgbG93ZXIgY2FzZSBjaGFyYWN0ZXJzIG9mIHRoZSBlbmdsaXNoIGFscGhhYmV0IChhLXopLCBhbmQgdGhlIG51bWJlciBvZiBjaGFyYWN0ZXJzIGluIGFueSBvZiB0aGUgc3RyaW5ncyBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMjAwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBLLCAxICZsZTsgSyAmbGU7IDEwMCwgdGhlIGRpc3RhbmNlIG9mIHRoZSBibGFuayBhbmQgdGhlIG90aGVyIGNoYXJhY3RlcnMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IG9uIG9ubHkgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBzaG91bGQgY29uc2lzdCBvZiB0aGUgc21hbGxlc3QgZGlzdGFuY2UgYXMgZGVmaW5lZCBpbiB0aGUgdGV4dCBvZiB0aGUgdGFzay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=
