[1일 1알고] S4 25288 영어 시험

 

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

 

LCS가 N이될 수 있는 경우를 모두 만족하는 가장 짧은 문자열을 구하는 문제입니다.

 

다만 주어진 문자에대한 모든 경우의 수를 만족해야합니다.

예를 들어 abc가 주어지고 N이 3이라면 aaa, aab ,aac, aba, abb, abc, aca, acb, acc, ... 이 모두 들어가야한다는 것입니다.

 

이를 모두 부분수열로 가지면서 가장 짧기 위해서는 어떻게 해야할까요?

 

바꿔서 보면 이 문제는 중복 순열을 구하는 것과 비슷합니다.

주어진 문자열의 각 문자가 중복이 가능하며 이를 N번 뽑는 것이니까요

경우의 수()를 구하라고 한다면, S(문자열).size()^N이 될것입니다.

 

그렇다면 문자를 중복해서 뽑는 것 처럼 문자열을 중복해서 이어붙인다면 이와 비슷한 효과를 줄 수 있을 것입니다.

예를 들어 N이 2이고 S가 abc라면 abcabc를 만들면 앞의abc에서 하나, 뒤의 abc에서 문자 하나를 뽑아 조합할 수 있기 때문에 LCS가 N인 모든 문자열을 만들 수 있을 것입니다.

---

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S;
    cin >> S;

    for (int i = 0; i < N; ++i)
    {
        cout << S;
    }

    return 0;
}