[C++] 백준 9177번 단어 섞기 – DP (Dynamic Programming)

🔍 문제 요약

• 문제 링크: 백준 9177
• 주요 태그: 문자열, 다이나믹 프로그래밍

탁자 위에 놓인 두 문자열 순서를 흐트러뜨리지 않고 섞어서(target interleaving) 세 번째 문자열을 만들 수 있는지 판별는 문제

---

💡 문제 분석

• “두 문자열을 순서를 유지하면서 섞는다”는 Interleaving String 문제
• T개의 데이터 세트가 주어지고, 각 세트마다 first second word가 공백으로 구분되어 들어온다.
  • word의 길이가 first + second와 다르면 무조건 불가능하다.
• 접두사 기준의 DP로 자주 풀린다.
• dp[i][j]를 first의 앞 i글자, second의 앞 j글자를 섞어 word의 앞 (i+j)글자를 만들 수 있는지 여부로 정의.

---

 

🔑 아이디어

1. 2차원 DP
   • 상태:
   • dp[i][j] = true ⇔ first[0..i-1] 와 second[0..j-1]를 interleaving 해 word[0..i+j-1] 를 만들 수 있다.
   • 점화식:
   • dp[0][0] = true; dp[i][j] = (first[i-1] == word[i+j-1] && dp[i-1][j]) // first에서 글자 사용 ||(second[j-1] == word[i+j-1] && dp[i][j-1]); // second에서 글자 사용
   • 초기화:
     • dp[i][0]는 first만으로 word 접두사 만들기
     • dp[0][j]는 second만으로 word 접두사 만들기
2. 1차원 DP (공간 최적화)
   • 두 번째 문자열 길이를 B라 할 때, vector<char> dp(B+1) 한 줄만으로 dp[j] 갱신
   • “위쪽”(한 행 전) 값을 임시 변수 prev에 저장하고, “왼쪽”(같은 행, dp[j-1]) 과 조합해 덮어쓴다.

---

🧩 풀이 전략

1. `word` != `first` + `second` → 즉시 no
2. 2차원 DP 또는 1차원 DP로 dp 표 채우기
3. 최종 결과는
   • 2D: dp[|first|][|second|]
   • 1D: dp[|second|]
4. true → yes, false → no

---

📦 예제 입력 & 출력

입력 예시:

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

 

출력 예시:

Data set 1: yes
Data set 2: yes
Data set 3: no

// Data set k: yes  또는 Data set k: no
// (k는 입력된 테스트케이스 순서)

---

🖥️ 코드

//2차원 DP

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

bool interleave2D(const string& a, const string& b, const string& w) {
    int A = a.size(), B = b.size();
    vector<vector<char>> dp(A+1, vector<char>(B+1, 0));
    dp[0][0] = 1;

    // 첫 열(i,0) 초기화
    for (int i = 1; i <= A; ++i)
        dp[i][0] = dp[i-1][0] && (a[i-1] == w[i-1]);
    // 첫 행(0,j) 초기화
    for (int j = 1; j <= B; ++j)
        dp[0][j] = dp[0][j-1] && (b[j-1] == w[j-1]);

    for (int i = 1; i <= A; ++i) {
        for (int j = 1; j <= B; ++j) {
            dp[i][j] = (a[i-1] == w[i+j-1] && dp[i-1][j])
                    || (b[j-1] == w[i+j-1] && dp[i][j-1]);
        }
    }
    return dp[A][B];
}



// 1차원 DP
bool interleave1D(string a, string b, const string& w) {
    // b가 더 짧도록 스왑
    if (a.size() < b.size()) swap(a, b);
    int A = a.size(), B = b.size();
    vector<char> dp(B+1, 0);

    dp[0] = 1;
    // j = 1 .. B 초기화
    for (int j = 1; j <= B; ++j)
        dp[j] = dp[j-1] && (b[j-1] == w[j-1]);

    for (int i = 1; i <= A; ++i) {
        char prev = dp[0];  // 위쪽 값 저장
        dp[0] = prev && (a[i-1] == w[i-1]);
        for (int j = 1; j <= B; ++j) {
            char up = dp[j];    // 위쪽
            char left = dp[j-1]; // 왼쪽 (이미 갱신됨)
            dp[j] = (a[i-1] == w[i+j-1] && up)
                  || (b[j-1] == w[i+j-1] && left);
        }
    }
    return dp[B];
}

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

    int T; cin >> T;
    for (int k = 1; k <= T; ++k) {
        string first, second, word;
        cin >> first >> second >> word;

        bool ok = (word.size() == first.size() + second.size())
               && interleave1D(first, second, word);  // 1D 버전 사용
        cout << "Data set " << k << ": " << (ok ? "yes\n" : "no\n");
    }
    return 0;
}

---

✅ 검증 및 테스트

• 단위 테스트:
  • first, second 중 하나가 빈 문자열
  • 중복된 문자 및 완전히 다른 문자 조합
  • word 길이 불일치
• 랜덤 검증:
  • 임의 first, second를 합친 문자열을 무작위로 섞어 yes 확인
  • 한 글자 변경해 no 확인

---

⏱️ 시간복잡도

구현 시간 공간

구현	시간	공간
2D DP	O(A×B)O(A \times B)	O(A×B)O(A \times B)
1D DP	O(A×B)O(A \times B)	O(min⁡(A,B))O(\min(A, B))

• A=∣first∣A = |first|, B=∣second∣B = |second|
• 제약: A,B≤200A, B \le 200, T≤1000T \le 1000 → 2002×1000=4×107200^2 \times 1000 = 4\times10^7 연산, 1초 내 충분

---

✨ 결론

• 전형적 “Interleaving String” DP로,
• 2D DP는 구현이 직관적이고 디버깅이 쉽고,
• 1D DP는 메모리를 200×200\times 절약하며 대규모 입력에서도 유리하다.