PS/종만북

합친 LIS - DP

2022. 10. 14. 12:18

이미 비슷한 문제를 푼 적이 있다. LIS 문제를 풀어보았다. 비슷한 형태의 문제들은 비슷한 부분 문제 정의를 사용해 풀 수 있는 경우가 많다.

 

기존 LIS를 푸는 문제 f는 다음과 같았다.

  • f(start_idx) : start_idx 위치의 수에서 시작하는 LIS 개수 리턴

합친 LIS를 푸는 문제 f의 정의를 다음과 같이 정의한다.

  • f(indexA, indexB) : indexA와 indexB 위치의 수에서 시작하는 합친 LIS 개수 리턴

indexA와 indexB위치의 수에서 시작하므로 다음에 오는 수는 indexA, indexB 위치의 수들보다 더 커야한다. 따라서 아래의 점화식이 만족한다. nextA는 다음에 올 수 있는 A의 수들의 인덱스이며 nextB도 다음에 올 수 있는 B의 수들의 인덱스이다. 

  • f(indexA, indexB) = max( max( f(nextA,indexB) + 1 ), max( f(indexA,nextB) + 1 ) )

점화식을 세웠다해도 구현이 살짝 복잡하다. LIS를 구할때 f(-1)은 -∞수에서 시작하는 LIS 개수를 리턴한다고 가정했던 것처럼 f(-1,-1)은  -∞수에서 시작하는 합친 LIS 개수를 리턴한다고 가정한다. 그러면 다음 부분 문제 f(nextA,-1)은  -∞, nextA 위치의 수를 시작하는 하는 합친 LIS 개수를 리턴할 것이고 f(-1,nextB)는 -∞, nextB 위치의 수에서 시작하는 합친 LIS 개수를 리턴할 것이다. f(-1,-1)은 다음 부분 문제가 리턴하는 가장 큰 합친 LIS 개수에 + 1을 리턴하면 된다. f(-1,-1)은 -∞수에서 시작하는 합친 LIS 개수를 리턴하므로 answer을 구할때 -1을 한다는 것에 주의하자.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int testCase = Integer.parseInt(br.readLine());

        for(int t=0; t<testCase; t++) {
            int n,m;
            st = new StringTokenizer(br.readLine(), " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            int[] A = new int[n];
            int[] B = new int[m];
            int[][] dp = new int[n+1][m+1];

            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<n; i++) A[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; i<m; i++) B[i] = Integer.parseInt(st.nextToken());

            for(int i=0; i<n + 1; i++)
                for(int j=0; j<m + 1; j++)
                    dp[i][j] = -1;

            int answer = 0;
            answer = f(-1,-1,A,B,dp) - 1;
            System.out.println(answer);
        }
    }

    static int f(int indexA, int indexB, int[] A, int[] B, int[][] dp) {
        if(dp[indexA + 1][indexB + 1] != -1) return dp[indexA + 1][indexB + 1];

        int answer = 1;
        long max_value;
        if(indexA == -1 && indexB == -1)
            max_value = (long)Integer.MIN_VALUE - 1;
        else if(indexA == -1)
            max_value = B[indexB];
        else if(indexB == -1)
            max_value = A[indexA];
        else
            max_value = Math.max(A[indexA], B[indexB]);

        for(int i=indexA+1; i<A.length; i++) {
            if(A[i] > max_value)
                answer = Math.max(answer, f(i,indexB,A,B,dp) + 1);
        }
        for(int i=indexB+1; i<B.length; i++) {
            if(B[i] > max_value)
                answer = Math.max(answer, f(indexA,i,A,B,dp) + 1);
        }
        dp[indexA + 1][indexB + 1] = answer;
        return answer;
    }
}

'PS > 종만북' 카테고리의 다른 글

단어 제한 끝말잇기 - DFS  (0) 2022.11.11
고대어 사전 - DFS  (0) 2022.11.03
최대 증가 수열(LIS) - DP  (0) 2022.10.11
출전 선수 정하기 - Greedy  (0) 2022.10.07
회의실 배정 - Greedy  (0) 2022.10.07
'PS/종만북' 카테고리의 다른 글
  • 단어 제한 끝말잇기 - DFS
  • 고대어 사전 - DFS
  • 최대 증가 수열(LIS) - DP
  • 출전 선수 정하기 - Greedy
gunjoon98
gunjoon98
gunjoon98
하루한방울
gunjoon98
전체
오늘
어제
  • 분류 전체보기 (139)
    • Computer Science (60)
      • Network (14)
      • DataBase (12)
      • Algorithm (14)
      • OS (9)
      • Computer Terminology (1)
      • DataStructure (10)
    • Spring (24)
      • Spring Basic (2)
      • Spring MVC (11)
      • Spring DB (4)
      • Spring Security (2)
      • Spring Test (1)
      • Spring Legacy (2)
      • 기타 (2)
    • Java (9)
      • Basic (7)
      • OOP (0)
    • WEB (14)
      • CSS (4)
      • JS (0)
      • HTTP (10)
    • PS (11)
      • 종만북 (10)
      • 모의 코테 (0)
      • 오답노트 (1)
    • Linux (6)
      • Ubuntu (6)
    • CM (5)
      • Git (5)
    • Project (0)
      • Deubot (0)
      • Scoreboard (0)
    • Infra (5)
      • Cloud (1)
      • CI&CD (3)
      • 쿠버네티스 (1)
    • Hadoop Echo System (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

hELLO · Designed By 정상우.
gunjoon98
합친 LIS - DP
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.