밑줄 넣기
시간 제한2초메모리 제한128 MB
주어진 N개의 단어 사이에 언더스코어를 넣어 전체 길이를 M으로 맞추되, 각 간격의 개수 차이가 1 이하가 되도록 하면서 특수한 문자 순서 기준으로 사전순 최소 문자열을 만드는 문제입니다.
문제
세준이는 주어진 N개의 영어 단어를 순서대로 이어 붙여 길이가 M인 새 단어를 만들려고 한다. 인접한 두 단어 사이에는 반드시 하나 이상의 _를 넣어야 한다.
새 단어의 길이가 M이 될 때까지 _를 더 넣을 수 있지만, _는 단어와 단어 사이에만 넣을 수 있다. 따라서 새 단어는 _로 시작하거나 끝날 수 없다.
단어 사이에 들어가는 _의 개수는 가능한 한 모두 같아야 한다. 모두 같게 만들 수 없다면, 단어 사이의 _ 개수 중 최댓값과 최솟값의 차이가 정확히 1이 되도록 해야 한다.
조건을 만족하는 새 단어 중 사전 순으로 가장 앞서는 단어를 출력하라.
입력
첫째 줄에 단어의 개수 N과 만들어야 하는 단어의 길이 M이 주어진다. 둘째 줄부터 N개의 줄에 영어 단어가 한 줄에 하나씩 주어진다.
출력
조건을 만족하는 새 단어 중 사전 순으로 가장 앞서는 단어를 한 줄에 출력한다.
문자의 사전 순서는 다음과 같다.
'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z'
제한
- 2 <= N <= 10
- 3 <= M <= 200
- 각 단어는 알파벳 대문자와 소문자로만 이루어져 있다.
- 각 단어의 길이는 1 이상 10 이하이다.
- N개 단어 길이의 합을 len이라고 할 때, len + N - 1 <= M을 만족한다.