https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
코드설명
DP와 LDS(Longest Decreasing Subsequence) 문제입니다.
우리가 구하는것은 각 위치에서의 수열의 감소하는 부분 수열의 개수이므로
6
10 30 10 20 20 10
dp[] = 1 1 2 2 2 3
위의. 로직을 구현해보았습니다.
처음에 DP값은 위의 로직을 구현하였지만, 가장 긴 감소하는 부분 수열을 구하는 과정에서 단순히
dp[N] 값을 출력함으로써 틀렸습니다.
아래와 같이 모든 dp값을 순회하면서 answer값을 갱신해야합니다.
for(int i=0;i<N;i++) {
answer = Math.max(dp[i], answer);
}
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] dp;
public static int[] arr;
public static int answer;
public static int MOD = 10007;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
dp = new int[N];
arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i=0;i<N;i++) {
dp[i] = 1;
for(int j=0; j<i;j++) {
if(arr[i] < arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
for(int i=0;i<N;i++) {
answer = Math.max(dp[i], answer);
}
System.out.println(answer);
}
}
재귀와 메모이제이션을 활용한 코드입니다.
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 {
static int N, C, H, W, K, M, T;
static int[] arr;
static int answer = 0;
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());
N = Integer.parseInt(st.nextToken());
arr = new int[N];
cache = new int[N+1];
Arrays.fill(cache, -1);
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.println(LIS(-1) - 1);
}
static int LIS(int now) {
if(cache[now + 1] != -1) return cache[now+1];
int ret = 1;
for(int next = now + 1; next < N; next++) {
if(now == -1 || arr[now] > arr[next]) {
ret = Math.max(ret, LIS(next) + 1);
}
}
return cache[now + 1] = ret;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 16922 로마 숫자 만들기- 브루트포스 JAVA (0) | 2023.09.16 |
---|---|
[백준] 13398 연속합 2 - DP JAVA (0) | 2023.09.15 |
[백준] 11057 오르막 수 - DP JAVA (0) | 2023.09.15 |
[백준] 1309 동물원 - 동적계획법(Dynamic Programming, DP) JAVA (0) | 2023.09.14 |
[백준] 15988 1, 2, 3 더하기 3 - 동적계획법(Dynamic Programming, DP) JAVA (0) | 2023.09.14 |