[LeetCode] 1035. Uncrossed Lines

https://leetcode.com/problems/uncrossed-lines/

Uncrossed Lines - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

• nums1[i] == nums2[j], and
• the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

 

배열 nums1과 nums2가 주어진다. 같은 수끼리 연결시킬 수 있고, 선 끼리는 겹칠 수 없다.

연결할 수 있는 최대의 선 개수를 구하여라.

 

 

풀이

nums1과 nums2의 2차원 배열을 생성한 뒤, 두 요소가 같으면 숫자 1을 더하는 식의 다이나믹 프로그래밍으로 구현한다.

만약 두 요소가 같지 않으면 이전 행이나 이전 열에서 최대값을 가져와 저장한다.

2차원 배열의 끝에는 nums1과 nums2를 모두 순회한 값이 누적되어있다.

 

코드(C++)

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(nums1[i] == nums2[j]){
                    dp[i+1][j+1] = dp[i][j]+1;
                }
                else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[n][m];
    }
};