백준 25328 (C++) 문자열 집합 조합하기

최초 업로드: 2025-10-22 12:39:49

최근 수정 시간: 2025-10-22 12:39:49

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] 문자열 집합 조합하기

[문제 링크](https://www.acmicpc.net/problem/25328)

## 문제 설명

알파벳 소문자로 구성된 문자열 X, Y, Z가 주어진다. 각각의 문자열에는 중복된 문자가 존재하지 않는다. 문자열 S에 있는 문자 중 임의로 k개를 선택하여 문자열 S에서의 순서를 유지하여 만든 모든 부분 문자열을 모아 놓은 집합을 문자열 S에 대한 조합 C(S, k)라고 하자. 예를 들어, 문자열 S = 'abc'에 대한 조합 C(S, 2) = {'ab', 'ac', 'bc'}이다. 입력으로 문자열 X, Y, Z와 정수 k가 주어질 때 C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력하자.

## 입력

첫 번째 줄에 문자열 X가 주어진다.

두 번째 줄에 문자열 Y가 주어진다.

세 번째 줄에 문자열 Z가 주어진다.

네 번째 줄에 정수 k가 주어진다.

## 출력

C(X, k), C(Y, k), C(Z, k)에 두 번 이상 나타나는 부분 문자열을 오름차순으로 출력한다. 한 줄에 하나의 부분 문자열을 출력한다. 두 번 이상 나타나는 부분 문자열이 없으면 -1을 출력한다.

## 풀이
최대 경우의 수가 17C8 이기 때문에 백트래킹 + set으로 해결 가능합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int k;
set<string> cur, res;

void back(string x, int depth=0, int start=0, string s="") {
 if(depth==k) {
 if(cur.count(s)) res.insert(s);
 cur.insert(s);
 return;
 }
 for(int i=start;i<x.size();i++) back(x, depth+1, i+1, s+x[i]);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 string x, y, z; cin >> x >> y >> z >> k;
 back(x); back(y); back(z);
 if(res.empty()) cout << -1;
 else for(string s:res) cout << s << '\n';
}
```