백준 1474 밑 줄

https://www.acmicpc.net/problem/1474

#include <iostream>
#include <vector>

using namespace std;

vector<string> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int cnt = 0;

    cin >> n >> m;

    arr.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        cnt += arr[i].size();
    }

    int underq = (m - cnt) / (n - 1);
    int underr = (m - cnt) % (n - 1);


    for (int i = 1; i < n; i++) {
        if (underr > 0 && islower(arr[i][0])) {
            arr[i] = '_' + arr[i];
            underr--;
        }
    }

    for (int i = n - 1; i > 0; i--) {
        if (underr>0 && isupper(arr[i][0])) {
            arr[i] = '_' + arr[i];
            underr--;
        }
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < underq; j++) {
            arr[i] = '_' + arr[i];
        }
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i];
    }




    return 0;
}

1. 문제

n개의 단어가 주어진다. 이를 연결하여 새로운 단어를 만들려고 하는 데, 이 때 다음의 조건을 따른다고 하자.

• _는 단어와 단어 사이에만 추가할 수 있다.
• 단어와 단어 사이의 _ 개수는 모두 같아야 한다. 불가능할 경우 각 단어 사이의 _의 최솟값과 최댓값의 차이는 1이 되어야 한다.
• 새 단어로 사전을 만든다고 할 때, 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 의 순서를 따른다

위 규칙으로 단어를 하나 만든다고 할 때, 사전 순으로 가장 앞서는 단어를 출력하라.

2. 풀이

n개의 단어를 이어붙이고, _를 추가하여 m개를 만드려면 n개 단어의 총 길이와 m 사이를 _를 적절하게 사용하여 채우는 식으로 해결할 수 있다.

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        cnt += arr[i].size();
    }

    int underq = (m - cnt) / (n - 1);
    int underr = (m - cnt) % (n - 1);

우선 필요한 _의 수를 단어 사이의 간격으로 나눈다. _의 최소 개수를 모든 단어 사이에 넣고, 나머지를 적절히 분배하여 최대 개수를 만들 것이다.

    for (int i = 1; i < n; i++) {
        if (underr > 0 && islower(arr[i][0])) {
            arr[i] = '_' + arr[i];
            underr--;
        }
    }

_는 소문자보다 높은 우선 순위를 가지고 있으므로 사전 순으로 가장 앞서는 단어를 만들려면 최대한 소문자로 시작하는 단어보다 앞에 배치되어야 한다. 이를 그리디하게 처리한다.

    for (int i = n - 1; i > 0; i--) {
        if (underr>0 && isupper(arr[i][0])) {
            arr[i] = '_' + arr[i];
            underr--;
        }
    }

 위 로직을 모두 처리했음에도 나머지(_가 들어가야 할 개수)가 남아있다면, 대문자로 시작하는 단어의 앞에 분배해야 하는데, 대문자보다 _가 우선순위에서 밀리므로 뒤에서부터 채워야 한다.

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < underq; j++) {
            arr[i] = '_' + arr[i];
        }
    }

 이를 모두 처리했다면 모든 단어 사이에 대해 _의 최소 개수(몫)만큼 _를 추가한다. 

    for (int i = 0; i < n; i++) {
        cout << arr[i];
    }

완성된 결과를 이어붙여 출력하면 정답을 구할 수 있다.