백준 9251번 LCS

🔒[문제 url]

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

🔑알고리즘

문자열 내 작은 범위에서의 LCS가, 큰 범위에서의 LCS에도 영향을 미치므로 해당 문제는 Dynamic Programming임을 알 수 있다.
따라서 점화식을 찾는 것이 핵심

• 어떻게 점화식을 찾는가?
  • 즉, 무엇을 기억하며 문제의 크기를 키워나가는가?
    문자열 A(=abcde)와 문자열 B(=bde)의 LCS를 구한다고 가정하자.
    
    이중 for문으로 각 문자열을 순회한다. 이때, 우리는 두 가지 상황을 만난다.
    • 1) A의 문자와 B의 문자가 같은 경우
    • 2) A의 문자와 B의 문자가 다른 경우
      
      
  • 1)의 경우, A직전 지점과 B직전 지점까지의 LCS에 1이 추가됨을 알 수 있다.
    • 예를 들어, A에서 d지점과 B에서 d지점을 방문한 경우,
      A 직전 지점인 c와 B 직전 지점인 b에서의 LCS는 1이므로,
      현재 지점에서의 LCS는 1을 더한 2가 됨을 알 수 있다.
      
      
  • 2)의 경우, (A 지점과 B직전 지점)과 (B 지점과 A직전 지점)에서의 LCS중 큰 값이 유지됨을 알 수 있다.
    - 현재 지점의 값이 달라 LCS가 증가하지는 않으므로, 가장 최근값 중 최대값을 가져온다.
    
    
• dp[ x ][ y ] : B의 x 지점과 A의 y 지점까지에서의 LCS
  • 위 알고리즘에 따라 이중for문을 순회한 후 dp 배열의 모습이다.
    
    
  • 아래는 예제 입력1 에서의 dp 배열 모습이다.
    

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <string>
#include <algorithm>

string A, B;
int dp[1001][1001]; // dp[x][y] : A[y]와 B[x]의 LCS

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> A >> B;
}



void SOLVE()
{

	for (int i = 0; i < B.length(); i++)
	{ // B가 행 : 세로 배치
		for (int j = 0; j < A.length(); j++)
		{ // A가 열 : 가로 배치

			// dp용 좌표 설정
			int x = i + 1, y = j + 1;

			// A과 B의 현재 지점에서 문자가 같다면, 이전 지점에서의 dp값 + 1
			if (A[j] == B[i])
				dp[x][y] = dp[x - 1][y - 1] + 1;
			// 다르다면, (A 현재 B 이전 지점 dp)와 (B 현재 A 이전 지점 dp)중 큰 값을 가져온다.
			else dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]);
		}
	}
	
	// B가 행, A가 열
	cout << dp[B.length()][A.length()];
}

int main()
{
	INPUT();

	SOLVE();
}

알고리즘을 이해했다면, 코드 구현은 쉽기때문에 부분 코드를 따로 작성하지 않았다. 코드가 이해가지 않는다면 알고리즘 설명을 다시 보길 권한다.
dp 갱신에서 out of range가 발생하지 않도록

// dp용 좌표 설정
int x = i + 1, y = j + 1;

좌표 처리를 따로 해준 것 정도만 유의하자.

🥇문제 후기

나는 알고리즘 중 DP를 정말 기가 막히게 못한다.
단순한 자기비하가 아니라 객관적으로 유독 DP에 약한 것같다.
점화식 찾으면 끝인걸 알지만, 그 점화식 찾는게 왜 이렇게 어려울까..
이 문제도 고생 참 많이 했다.
그래도 나만 어려운거 아니니까 연습 많이 해야지..!