2706번 - 문자 보내기 스페셜 저지다국어

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

문제

표준 휴대전화의 키패드에는 글자들이 다음과 같이 번호키와 대응되어있다.

글자 C를 입력하기 위해서는 '2'키를 3번 눌러야 한다. 이와 같이 글자를 입력하기 위해 눌러야 하는 키의 번호와 눌러야 하는 횟수는 글자가 어떤 키의 리스트에 속해있는가와 리스트에서 몇 번째인지에 따라 다르다.

Exupery Telephone Company (ETC)는 축적된 글자별 사용 빈도 데이터베이스를 이용하여 휴대전화 사용자들의 평균 키 입력 횟수를 줄이기 위해 글자 배치들을 변경하려고 한다. 예를 들어, S를 7키에서 8키로 옮길 수 있다. 

글자들이 나타나는 순서는 알파벳 순서를 지켜야 하지만 각 키마다 배정되는 글자의 수는 달라도 된다.

각 알파벳의 빈도수와 키의 개수가 주어졌을 때, 알파벳을 어떻게 배치해야 입력 회수의 평균값이 작아지는지 구하는 프로그램을 작성하시오.

각 키에 알파벳은 적어도 한 개 있어야 하며, 많아야 여덟 개까지 있을 수 있다.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다: 첫째 줄에는 키의 개수 K가 주어진다 (4 ≤ K ≤ 26) 둘째 줄에는 첫 13개 알파벳의 사용 빈도가 주어진다. 셋째 줄에는 마지막 13개 알파벳의 사용 빈도가 주어진다.

출력

각 테스트 케이스에 대해 최적의 키 배열에서의 평균 키 입력 횟수(소수점 셋째자리까지), A~Z의 배열을 공백을 사이에 두고 출력한다.

예제 입력 1 

2
8
8.167 1.492 2.782 4.253 12.702 2.228 2.015 6.094 6.966 0.153 0.772 4.025 2.406
6.749 7.507 1.929 0.095 5.987 6.327 9.056 2.758 0.978 2.360 0.150 1.974 0.075
9
1.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
10.0 10.0 10.0 10.0 10.0 11.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0

예제 출력 1 

1.647 AB CD EFG HIJK LM NOPQ RS TUVWXYZ
1.570 A B CDEFG HIJKLM N OP QR STUV WXYZ
W3sicHJvYmxlbV9pZCI6IjI3MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTAgXHViY2Y0XHViMGI0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ0NWNcdWM5MDAgXHVkNzM0XHViMzAwXHVjODA0XHVkNjU0XHVjNzU4IFx1ZDBhNFx1ZDMyOFx1YjRkY1x1YzVkMFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI0ZTRcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJjODhcdWQ2MzhcdWQwYTRcdWM2NDAgXHViMzAwXHVjNzUxXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleS5wbmdcIiBzdHlsZT1cIndpZHRoOiAyMjVweDsgaGVpZ2h0OiAyNjNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhZTAwXHVjNzkwIENcdWI5N2MgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCAmIzM5OzImIzM5O1x1ZDBhNFx1Yjk3YyAzXHViYzg4IFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZTAwXHVjNzkwXHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWQwYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVkNjlmXHVjMjE4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVkMGE0XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWMxOGRcdWQ1NzRcdWM3ODhcdWIyOTRcdWFjMDBcdWM2NDAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1YmE4NyBcdWJjODhcdWM5ZjhcdWM3NzhcdWM5YzBcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0RXh1cGVyeSBUZWxlcGhvbmUgQ29tcGFueSAoRVRDKVx1YjI5NCBcdWNkOTVcdWM4MDFcdWI0MWMgXHVhZTAwXHVjNzkwXHViY2M0IFx1YzBhY1x1YzZhOSBcdWJlNDhcdWIzYzQgXHViMzcwXHVjNzc0XHVkMTMwXHViY2EwXHVjNzc0XHVjMmE0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWQ3MzRcdWIzMDBcdWM4MDRcdWQ2NTQgXHVjMGFjXHVjNmE5XHVjNzkwXHViNGU0XHVjNzU4IFx1ZDNjOVx1YWRlMCBcdWQwYTQgXHVjNzg1XHViODI1IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM5MDRcdWM3NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWUwMFx1Yzc5MCBcdWJjMzBcdWNlNThcdWI0ZTRcdWM3NDQgXHViY2MwXHVhY2JkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgU1x1Yjk3YyA3XHVkMGE0XHVjNWQwXHVjMTFjIDhcdWQwYTRcdWI4NWMgXHVjNjJlXHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWUwMFx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjOWMwXHVjZjFjXHVjNTdjIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFjMDEgXHVkMGE0XHViOWM4XHViMmU0IFx1YmMzMFx1YzgxNVx1YjQxOFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NTggXHVjMjE4XHViMjk0IFx1YjJlY1x1Yjc3Y1x1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHViZTQ4XHViM2M0XHVjMjE4XHVjNjQwIFx1ZDBhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWJjMzBcdWNlNThcdWQ1NzRcdWM1N2MgXHVjNzg1XHViODI1IFx1ZDY4Y1x1YzIxOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWFjMTJcdWM3NzQgXHVjNzkxXHVjNTQ0XHVjOWMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFjMDEgXHVkMGE0XHVjNWQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YWMxYyBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVjNWVjXHViMzVmIFx1YWMxY1x1YWU0Y1x1YzljMCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNDogXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQwYTRcdWM3NTggXHVhYzFjXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICg0ICZsZTsgSyAmbGU7IDI2KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NhYiAxM1x1YWMxYyBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHVjMGFjXHVjNmE5IFx1YmU0OFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IDEzXHVhYzFjIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc1OCBcdWMwYWNcdWM2YTkgXHViZTQ4XHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHVjODAxXHVjNzU4IFx1ZDBhNCBcdWJjMzBcdWM1ZjRcdWM1ZDBcdWMxMWNcdWM3NTggXHVkM2M5XHVhZGUwIFx1ZDBhNCBcdWM3ODVcdWI4MjUgXHVkNjlmXHVjMjE4KFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWMxNGJcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzApLCBBflpcdWM3NTggXHViYzMwXHVjNWY0XHVjNzQ0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGV4dCBNZXNzYWdpbmcgSW1wcm92ZW1lbnQ/IiwiZGVzY3JpcHRpb24iOiI8cD5PbiBhIHN0YW5kYXJkIG1vYmlsZSBwaG9uZSB0aGUgbGV0dGVycyBhcmUgZGlzdHJpYnV0ZWQgYWNyb3NzIHRoZSBrZXlzIDIgdGhyb3VnaCA5IGFzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tleS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNjNweDsgd2lkdGg6MjI1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VG8gZW50ZXIgdGhlIGxldHRlciBDLCB5b3UgcHJlc3Mga2V5IDIgdGhyZWUgdGltZXMgKHNlZWluZyBBLUItQykuIFRoZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyB0byBlbnRlciBhIGxldHRlciBkZXBlbmRzIG9uIHdoZXJlIGl0IGlzIGluIHRoZSBsaXN0IG9mIGxldHRlcnMgb24gaXRzIGtleS48XC9wPlxyXG5cclxuPHA+VGhlIEZsYXRoZWFkIFRlbGVwaG9uZSBDb21wYW55IChGVEMpIGlzIGNvbnNpZGVyaW5nIHJlYXJyYW5naW5nIHRoZSBsZXR0ZXJzIG9uIHRoZSBrZXlzIHRvIHJlZHVjZSB0aGUgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyByZXF1aXJlZCB0byBlbnRlciBuYW1lcyBldGMuIG9yIHNlbmQgdGV4dCBtZXNzYWdlcy4gVGhlIGxldHRlcnMgbXVzdCBzdGlsbCBhcHBlYXIgaW4gYWxwaGFiZXRpY2FsIG9yZGVyIG9uIHRoZSBrZXlzIGJ1dCBkaWZmZXJlbnQgbnVtYmVycyBvZiBsZXR0ZXJzIG1heSBhcHBlYXIgb24gZWFjaCBrZXkgYW5kIHBvc3NpYmx5IG1vcmUga2V5cyBjb3VsZCBiZSB1c2VkLiBGVEMgaGFzIHNldmVyYWwgZGF0YWJhc2VzIG9mIGxldHRlciBmcmVxdWVuY2llcyB1c2VkIGluIGRpZmZlcmVudCBhcHBsaWNhdGlvbnMuIEZvciBpbnN0YW5jZSwgaXQgbWlnaHQgaGVscCB0byBtb3ZlIFMgZnJvbSB0aGUgNyBrZXkgdG8gdGhlIDgga2V5LiBUaGV5IG5lZWQgYSBwcm9ncmFtIHdoaWNoIGlzIGdpdmVuIHRoZSBmcmVxdWVuY2llcyBvZiB0aGUgbGV0dGVycyBhbmQgYSBudW1iZXIgb2Yga2V5cyBhbmQgcmV0dXJucyB0aGUgYXNzaWdubWVudCBvZiBsZXR0ZXJzIHRvIGtleXMgd2l0aCB0aGUgc21hbGxlc3QgYXZlcmFnZSBudW1iZXIgb2Yga2V5c3Ryb2tlcyB1c2luZyB0aGUgZ2l2ZW4gZnJlcXVlbmNpZXMuIEVhY2gga2V5IHVzZWQgbXVzdCBoYXZlIGF0IGxlYXN0IG9uZSBsZXR0ZXIgYW5kIGF0IG1vc3QgZWlnaHQgbGV0dGVycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgdGhyZWUgbGluZXMgb2YgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgSywgKDQgJmxlOyBLICZsZTsgMjYpLCB0aGUgbnVtYmVyIG9mIGtleXMgd2hpY2ggYXJlIHRvIGJlIHVzZWQuIFRoZSBzZWNvbmQgYW5kIHRoaXJkIGxpbmVzIGNvbnRhaW4gMTMgZGVjaW1hbCB2YWx1ZXMgZWFjaCBnaXZpbmcgdGhlIHBlcmNlbnQgZnJlcXVlbmN5IG9mIHRoZSBsZXR0ZXJzIEEgdGhyb3VnaCBaIGluIG9yZGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCB5b3Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YSBzZXQgbnVtYmVyIGFzIGEgZGVjaW1hbCBpbnRlZ2VyIChzdGFydCBjb3VudGluZyBhdCBvbmUpLCB0aGUgYmVzdCBhdmVyYWdlIG51bWJlciBvZiBrZXlzdHJva2VzIHRvIHRocmVlIGRlY2ltYWwgcGxhY2VzLCBhIHNwYWNlIGFuZCB0aGUgbGV0dGVycyBBIHRocm91Z2ggWiwgZm9yIHRoZSBiZXN0IGFycmFuZ2VtZW50LCBpbiBvcmRlciB3aXRoIGEgc2luZ2xlIHNwYWNlIGF0IHRoZSBicmVhayBiZXR3ZWVuIGxldHRlcnMgb24gZGlmZmVyZW50IGtleXMuIEl0IGlzIHBvc3NpYmxlIHRoYXQgdGhlIHNhbWUgaW5wdXQgZGF0YSBzZXQgbWF5IHByb2R1Y2UgZGlmZmVyZW50IG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > Greater New York Region > 2008 Greater New York Programming Contest E번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

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

한국어 | English (Beta)