문제 설명
두 개의 수평선 위에 정수 배열 A와 B가 주어진 순서대로 적혀 있다고 가정해 봅시다. 이제 두 숫자 A[i]와 B[j]를 잇는 연결선을 그릴 수 있는데, 이때 다음 조건을 만족해야 합니다.
- A[i] == B[j] 여야 합니다.
- 그려지는 선은 다른 어떤 연결선(수평선은 제외)과도 교차해서는 안 됩니다.
주의할 점은 연결선이 끝점에서도 서로 교차할 수 없다는 것입니다. 즉, 각 숫자는 오직 하나의 연결선에만 속할 수 있습니다. 우리의 목표는 그릴 수 있는 연결선의 최대 개수를 구하는 것입니다.
예를 들어 입력이 [1,4,2]와 [1,2,4]라면 출력은 2가 됩니다.
| 1 | 4 | 2 |
| 1 | 2 | 4 |
위 표에서 볼 수 있듯이 교차하지 않는 선 2개를 그릴 수 있습니다. 3개를 그릴 수 없는 이유는 A[1]=4에서 B[2]=4로 이어지는 선이 A[2]=2에서 B[1]=2로 이어지는 선과 반드시 교차하기 때문입니다.
풀이 접근 방법
이 문제는 메모이제이션(memoization)을 활용한 재귀적 동적 계획법(DP)으로 해결할 수 있습니다. 핵심 아이디어는 각 위치에서 현재 숫자를 매칭하거나 건너뛰는 두 가지 선택지 중 더 나은 결과를 선택하는 것입니다.
- solve() 메서드를 정의합니다. 이 메서드는 인덱스 i, j, 배열 A, 배열 B, 그리고 dp 행렬을 인자로 받습니다.
- i가 배열 A의 범위를 벗어나면 0을 반환합니다.
- j가 배열 B의 범위를 벗어나면 0을 반환합니다.
- nj := j 로 초기화한 뒤, nj가 B의 크기 미만이고 B[nj]가 A[i]와 같지 않은 동안 nj를 1씩 증가시킵니다.
- temp는 nj가 B의 크기 미만일 때 1, 그렇지 않으면 0으로 설정합니다.
- ret := max(solve(i+1, j, A, B, dp), temp + solve(i+1, nj+1, A, B, dp)) 로 계산합니다. 즉, 현재 숫자를 매칭하는 경우와 건너뛰는 경우 중 최댓값을 구합니다.
- dp[i][j]에 ret을 저장하고 반환하여 중복 계산을 방지합니다.
메인 메서드에서는 다음과 같이 진행합니다.
- n := A의 크기, m := B의 크기로 설정합니다.
- n × m 크기의 dp 행렬을 생성하고 모든 값을 -1로 초기화합니다.
- solve(0, 0, A, B, dp)를 호출하여 결과를 얻습니다.
C++ 구현 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int i, int j, vector<int>&A, vector<int>&B, vector<vector<int>>& dp){
if(i >= A.size()) return 0;
if(j >= B.size()) return 0;
if(dp[i][j] != -1) return dp[i][j];
int nj = j;
while(nj < B.size() && B[nj] != A[i]) nj++;
int ret = max(solve(i + 1, j, A, B, dp), (nj < B.size() ? 1 : 0) + solve(i + 1, nj + 1, A, B, dp));
return dp[i][j] = ret;
}
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
int n = A.size();
int m = B.size();
vector<vector<int>> dp(n, vector<int>(m, -1));
return solve(0, 0, A, B, dp);
}
};
main(){
vector<int> v1 = {1,4,2};
vector<int> v2 = {1,2,4};
Solution ob;
cout << (ob.maxUncrossedLines(v1, v2));
}입력
[1,4,2] [1,2,4]
출력
2
이처럼 동적 계획법과 메모이제이션을 결합하면 모든 가능한 매칭 조합을 효율적으로 탐색하면서도 중복 계산을 피할 수 있어, 시간 복잡도 O(N×M) 안에 최적의 답을 구할 수 있습니다.