https://www.algospot.com/judge/problem/read/JLIS
algospot.com :: JLIS
합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로
www.algospot.com
코드설명
동적계획법을 활용합니다.
이 문제의 경우 이전 LIS의 문제와 같이 처음에 풀어보려했습니다만, 중요한 부분을 놓쳤습니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static final long NEGINF = Long.MIN_VALUE;
public static int[] A, B;
public static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N]; B = new int[M];
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());
answer = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
answer = Math.max(answer, jLis(0, i, j));
}
}
System.out.println(answer);
}
}
public static int jLis(int level, int indexA, int indexB) {
//기저사례 : 없음. 이미 for문에서 N과 M 이상으로 호출되도록 하지 않기 떄문임.
//또한 A[N]이 된다면 메모리 없는 부분을 호출하는 것임.
//기본값을 2로 설정하여 최소 길이를 보장합니다.
int ret = 2;
long a = A[indexA];
long b = B[indexB];
long maxElement = Math.max(a, b);
for(int nextA = indexA + 1; nextA < N; nextA++) {
if(maxElement < A[nextA]) {
ret = Math.max(ret, jLis(level + 1, nextA, indexB) + 1);
}
}
for(int nextB = indexB + 1; nextB < M; nextB++) {
if(maxElement < B[nextB]){
ret = Math.max(ret, jLis(level + 1, indexA, nextB) + 1);
}
}
return ret;
}
}어떤 점이 틀렸을까요?
바로 이 JLIS는 두개의 LIS를 합치는 경우이므로 LIS의 시작위치를 반드시 -1 부터 시작해야만 합니다.
저는 위의 코드를 보면 반드시 indexA = 0, indexB = 0 시작점을 기준으로 하여, indexA와 indexB가 반드시 순서대로 들어가도록 작업한 것이 문제입니다.
아래의 예제를 보면 이해할 수 있습니다.
먼저 위의 코드로 풀어도 올바르게 나오는 경우입니다.
입력예시 1
1
3 3
1 9 4
3 4 7출력예시 1
5
위의 코드로 접근할시 틀리는 경우입니다.
입력 예시 2
1
3 3
1 2 4
3 4 7출력예시 2
5
위의 방법을 피하기 위해서, 함수의 시작 index가 -1이 되어야 합니다.
그렇게 처리하여 외부의 MAIN 함수에서 한번의 호출로 모든 경우를 탐색할 수 있고, 실제로
위의 예시 2번처럼
1 2 3 4 7 로 5가 나오도록 할 수 있습니다.
제가 작성한 첫번쨰 코드는
"1 3" 이 강제된 코드라고 생각하시면 됩니다.
두번쨰 코드는, 모든 경우의 수를 올바르게 탐색할 수 있도록 수정합니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static final long NEGINF = Long.MIN_VALUE;
public static int[] A, B;
public static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N]; B = new int[M];
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());
answer = 0;
answer = Math.max(answer, jLis(0, -1, -1) - 2);
System.out.println(answer);
}
}
public static int jLis(int level, int indexA, int indexB) {
//기저사례 : 없음. 이미 for문에서 N과 M 이상으로 호출되도록 하지 않기 떄문임.
//또한 A[N]이 된다면 메모리 없는 부분을 호출하는 것임.
//기본값을 2로 설정하여 최소 길이를 보장합니다.
int ret = 2;
long a = (indexA == -1 ? NEGINF : A[indexA]);
long b = (indexB == -1 ? NEGINF : B[indexB]);
long maxElement = Math.max(a, b);
for(int nextA = indexA + 1; nextA < N; nextA++) {
if(maxElement < A[nextA]) {
ret = Math.max(ret, jLis(level + 1, nextA, indexB) + 1);
}
}
for(int nextB = indexB + 1; nextB < M; nextB++) {
if(maxElement < B[nextB]){
ret = Math.max(ret, jLis(level + 1, indexA, nextB) + 1);
}
}
return ret;
}
}이 코드의 경우 의문이 갈 수 있는 점은 왜 모든 답을 구한뒤 -2 를 할까? 입니다.
여기서 우선 ret = 2 를 하는 이유는, 배열 A와 B에서 실제로 선택된 첫 번째 요소들이 증가하는 부분 수열의 일부로 계산될 수 있도록 하기 위함입니다. 항상 A[indexA]와 B[indexB]는 존재하기에 길이는 최하 2인 것 입니다.
다른 부분문제에 들어가서도 마찬가지입니다. 그렇기에 반한되는 최소값은 항상 2이겠지요.
2보다 작은 경우는 애초에 반환되지 않습니다. 만약 ret =2 로 설정하지 않는다면 굳이 -2 를 할필요도 없습니다. 하지만 로직에 맞지 않습니다.
위의 코드의 문제점은 무엇일까요?
여전히 시간초과가 발생합니다. 이유는 최적 부분 구조(optimal substructure)과 참조적 투명성의 특성으로 이루는 문제임을 알 수 있는데(즉, 이전의 결과가 이후의 함수 수행결과에 전혀 영향을 미치지 않습니다. indexA보다 작은 indexA - 1.. 값은 indexA값을 기반으로 하는 jLis에 전혀 영향을 미치지 않는다는 의미입니다.)
이러한 특성을 통해 만약 같은 인자를 가진 jLis가 호출된다면 메모이제이션을 활용하여 중복 부분 문제의 계산을 피할 수 있음을 알 수 있습니다.
그렇다면 메모이제이션을 적용한 코드입니다.
성공적으로 통과합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static final long NEGINF = Long.MIN_VALUE;
public static int[] A, B;
public static int[][] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N]; B = new int[M];
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());
cache = new int[101][101];
for(int i=0;i<101;i++) {
Arrays.fill(cache[i], -1);
}
answer = 0;
answer = Math.max(answer, jLis(0, -1, -1) - 2);
System.out.println(answer);
}
}
public static int jLis(int level, int indexA, int indexB) {
//기저사례 : 없음. 이미 for문에서 N과 M 이상으로 호출되도록 하지 않기 떄문임.
//또한 A[N]이 된다면 메모리 없는 부분을 호출하는 것임.
if(cache[indexA + 1][indexB + 1] != -1) return cache[indexA + 1][indexB + 1];
//기본값을 2로 설정하여 최소 길이를 보장합니다.
cache[indexA + 1][indexB + 1] = 2;
long a = (indexA == -1 ? NEGINF : A[indexA]);
long b = (indexB == -1 ? NEGINF : B[indexB]);
long maxElement = Math.max(a, b);
for(int nextA = indexA + 1; nextA < N; nextA++) {
if(maxElement < A[nextA]) {
cache[indexA + 1][indexB + 1]= Math.max(cache[indexA + 1][indexB + 1], jLis(level + 1, nextA, indexB) + 1);
}
}
for(int nextB = indexB + 1; nextB < M; nextB++) {
if(maxElement < B[nextB]){
cache[indexA + 1][indexB + 1] = Math.max(cache[indexA + 1][indexB + 1], jLis(level + 1, indexA, nextB) + 1);
}
}
return cache[indexA + 1][indexB + 1];
}
}위의 코드에서 주의깊게 살펴봐야할 점은 역시, A[-1] = -무한대로 설정함으로써 추가적인 설정입니다.
아래와 같이 처리함을 알 수 있습니다.
cache[indexA + 1][indexB + 1]이유는 A[-1]을 사실상 A[0]으로 판단하기에 -무한대 값을 A[0]에 삽입하고 나머지 값을 뒤로 밀었다고 생각하시면 됩니다.
이떄, 의문이 드는점은 왜 nextA값은 여전히 변화가 없을까?
for(int nextA = indexA + 1; nextA < N; nextA++) {
if(maxElement < A[nextA]) {
cache[indexA + 1][indexB + 1]= Math.max(cache[indexA + 1][indexB + 1], jLis(level + 1, nextA, indexB) + 1);
}
}한칸씩 뒤로 밀었다면 indexA + 1이 아닌 indexA + 2가 되어야 하는것이 아닐까? 라는 생각이 듭니다.
하지만, 이는 틀렸습니다.
이유는, A[0]번쨰에 -무한대의 값을 삽입함과 동시에 A[1]번쨰는 이전의 A[0]번쨰 값인 첫 시작값입니다.
우리는 현재 위치(indexA 혹은 indexB)의 다음 위치부터 탐색을 시작해야 합니다. 만약 indexB + 2로 시작한다면, 가능한 경우 중 하나를 건너뛰게 되어 정확한 JLIS를 찾을 수 없습니다.
예를 들어, B 배열에 [1, 3, 5]가 있고, 현재 indexB가 0일 때(즉, 현재 B 배열에서 고려하고 있는 값은 1입니다), indexB + 1에서 시작하면 다음 고려할 값은 3이 됩니다. 이것은 JLIS를 구성하는 데 유효한 후보입니다. 하지만 indexB + 2에서 시작한다면, 우리는 5부터 시작하게 되어, 3을 포함하는 가능한 JLIS를 놓치게 됩니다.
따라서, nextA = indexA + 1과 nextB = indexB + 1부터 시작하는 것은, 이전에 선택된 원소보다 큰 모든 가능한 원소를 고려하여, 가장 긴 증가하는 부분 수열을 찾기 위한 필수적인 접근 방식입니다. 이렇게 함으로써, 두 배열 A와 B에서 선택할 수 있는 모든 가능한 원소 조합을 고려하여, 최적의 해답을 찾아낼 수 있습니다.
그렇기에, 이와 같이 처리합니다.