# [Silver I] 밑 줄 [문제 링크](https://www.acmicpc.net/problem/1474) ## 문제 설명 <p>세준이는 N개의 영어 단어를 이용해 길이가 M인 새로운 단어를 만들려고 한다. 새로운 단어는 N개의 단어를 순서대로 이어 붙이고, 각 단어의 사이에 <code>_</code>을 넣어서 만든다. 이렇게 만든 새로운 단어의 길이가 M이 아닌 경우 <code>_</code>를 추가해서 길이가 M이 되게 만들어야 한다.</p> <ul> <li><code>_</code>는 단어와 단어 사이에만 추가할 수 있다. 따라서, 새로운 단어는 <code>_</code>으로 시작하거나, <code>_</code>로 끝날 수 없다.</li> <li>단어와 단어 사이에 있는 <code>_</code>의 개수는 모두 같아야 한다. <ul> <li>모두 같게 만드는 것이 불가능한 경우 단어와 단어 사이에 있는 <code>_</code>의 개수의 최댓값과 최솟값의 차이는 1이 되어야 한다.</li> </ul> </li> </ul> <p>새로운 단어 중 사전 순으로 가장 앞서는 단어를 구해보자.</p> ## 입력 <p>첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다.</p> ## 출력 <p>첫째 줄에 사전 순으로 가장 앞서는 단어를 출력한다.</p> <p>알파벳 대문자, 소문자, 밑 줄의 순서는 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이다.</p> ## 풀이 단어 사이에 공통으로 배치할 밑줄의 수를 제외하고, 그리디하게 앞에서부터 소문자로 시작하는 단어 앞에 밑줄을 넣고, 더 넣어야 하면 뒤에서부터 안 넣은 단어 앞에 밑줄을 추가로 넣으면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<string> s(n); for(int i=0;i<n;i++) { cin >> s[i]; m -= s[i].length(); } int extra = m%(n-1); for(int i=0;i<n;i++) { if(i!=0) { for(int j=0;j<m/(n-1);j++) cout << '_'; if(extra && (s[i][0]>='a' || n-i==extra)) cout << '_', extra--; } cout << s[i]; } } ```