# [Silver IV] 영어 시험 [문제 링크](https://www.acmicpc.net/problem/25288) ## 문제 설명 <p>정휘는 영어 시험에서 배점이 큰 서술형 문제의 답안을 apple 대신 aple이라고 써서 틀렸다. 한 글자 차이로 큰 점수를 잃은 정휘는 이런 채점 방식이 합리적이지 않다고 생각해서 선생님께 새로운 채점 기준을 제안하기로 했다.</p> <p>정휘는 응시자가 작성한 답안과 실제 정답의 "최장 공통 부분 수열"의 길이에 비례하게 점수를 주는 방식을 제안했다. 만약 정답이 apple인 문제에 aple을 적어서 내면 배점의 80%를 얻을 수 있고, apple을 적어서 내면 문제의 점수를 온전하게 받을 수 있다. 하지만 선생님은 정답을 구성하는 알파벳과 정답의 길이만 알면, 동일한 단어로 모든 문제를 풀 수 있는 문자열이 존재함을 지적하며 이 방식을 거절했다. 예를 들어 정답의 길이가 2이고 정답에 a와 b만 들어갈 수 있다면, abba를 이용해 모든 문제를 풀 수 있다.</p> <p>선생님이 거절하신 이유를 납득하지 못한 정휘는, 정답을 구성하는 알파벳들과 정답의 길이가 주어졌을 때 모든 답안에 대해 만점을 받을 수 있는 가장 짧은 문자열을 직접 만들어보기로 했다.</p> <p>최장 공통 부분 수열이 무엇인지 잘 모르는 친구들은 친절한 준서가 준비한 아래 정의를 읽어보도록 하자. 알파벳을 수라고 생각하면 문자열도 수열이다.</p> <ul> <li><strong>부분 수열</strong>이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.</li> <li>두 수열 $A, B$의 <strong>공통 부분 수열</strong>이란 $A$의 부분 수열이면서 동시에 $B$의 부분 수열인 수열을 말한다.</li> <li>두 수열 $A, B$의 <strong>최장 공통 부분 수열</strong>이란 $A, B$의 공통 부분 수열 중 가장 긴 수열을 말한다.</li> <li>예를 들어, appl와 aple의 최장 공통 부분 수열은 apl이다.</li> </ul> ## 입력 <p>첫째 줄에 정답의 길이 $N$이 주어진다. ($1 leq N leq 10,000$)</p> <p>둘째 줄에 정답을 구성하는 알파벳이 공백 없이 소문자로 주어진다. 각 알파벳은 최대 한 번 주어진다.</p> ## 출력 <p>모든 답안에 대해 만점을 받을 수 있는 가장 짧은 문자열을 출력한다.</p> <p>가능한 가장 짧은 문자열이 여러 가지인 경우 아무거나 출력한다.</p> ## 풀이 #### n개의 길이에 대해 모든 부분수열이 다 나오려면 문자열에 각 문자가 번갈아가면서 n개씩 있으면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; while(n--) cout << s; } ```