[ 백준 9251 ] LCS (C++) - DP

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. '최장 부분 공통 수열' 문제는 DP를 사용한다.
2. 어떻게 풀지 모르겠어서 구글링을 하여 아래 사이트에서 이해를 한뒤 풀었다. 주석을 풀면 myMap이 만들어진 것을 볼 수 있다.
   도움을 받은 사이트

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<string>

using namespace std;

string str1, str2;
//string answer = "";
int myMap[1001][1001];

void input() {
    cin >> str1 >> str2;
}

int sol() {
    for (int y = 1; y <= str1.size(); y++) {
        for (int x = 1; x <= str2.size(); x++) {
            if (str2[x - 1] == str1[y - 1]) {
                myMap[y][x] = myMap[y - 1][x - 1] + 1;
            }
            else {
                myMap[y][x] = max(myMap[y - 1][x], myMap[y][x - 1]);
            }
        }
    }

    int sx = str2.size();
    int sy = str1.size();
    int answer = 0;

    while (sx != 0 && sy != 0) {
        if (myMap[sy - 1][sx] == myMap[sy][sx]) {
            sy--;
        }
        else if (myMap[sy][sx - 1] == myMap[sy][sx]) {
            sx--;
        }
        else {
            answer++;
            sy--;
            sx--;
        }
    }
    return answer;
}

int main() {

    input();
    cout << sol() << endl;

    //for (int y = 1; y <= str1.size(); y++) {
    //    for (int x = 1; x <= str2.size(); x++) {
    //        cout << myMap[y][x] << " ";
    //    }
    //    cout << endl;
    //}

    return 0;
}

---

🤔 문제 후기

아직 DP관련 문제는 풀기가 어려웠다. 어떻게 풀어야 할지 알겠는데 모르겠는 느낌이랄까...? 구글링 하기 전에 구글링한 방식으로 풀면 되겠다고 생각은 했는데, 정확하게 어떻게?? 라는 생각이 들었다... 그래도 DP는 관련 문제들은 비슷한 점화식을 사용하니 다음에는 맞지 않을까 싶다.