문제 : https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
해당 문제는 수열 A 가 주어졌을때, 가장 긴 증가하는 부분 수열, LIS (Longest Increasing Subsequence) 의 길이를 구하는 문제이다.
다이나믹 프로그래밍에서 가장 중요한 것은 규칙을 찾거나, 일반식을 찾는 것이다.
먼저, arr[1] < arr[2] 이므로 dp[2] = dp[1] +1 을 대입한다.
1 | 2 | |
arr[i] | 10 | 20 |
dp[i] | 1 | 2 |
1 | 2 | 3 | |
arr[i] | 10 | 20 | 10 |
dp[i] | 1 | 2 | 1 |
arr[4]는 arr[2]보다 값도 크고, dp값도 2보다 작은 1이었으므로 dp[2] 값인 2에서 +1 해서 3을 넣는다.
1 | 2 | 3 | 4 | |
arr[i] | 10 | 20 | 10 | 30 |
dp[i] | 1 | 2 | 1 | 3 |
arr[5]도 같은 방법으로 진행한다.
1 | 2 | 3 | 4 | 5 | |
arr[i] | 10 | 20 | 10 | 30 | 20 |
dp[i] | 1 | 2 | 1 | 3 | 2 |
6번째까지 진행하면, dp값이 4가 최대임을 알 수 있다.
1 | 2 | 3 | 4 | 5 | 6 | |
arr[i] | 10 | 20 | 10 | 30 | 20 | 50 |
dp[i] | 1 | 2 | 1 | 3 | 2 | 4 |
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int [] arr = new int[N+1];
int [] dp = new int[N+1];
int cnt=1;
for (int i=0;i<N;i++){
arr[i]=sc.nextInt();
dp[i]=1;
}
for (int i=1;i<N;i++){
// 0 ~ i 이전 원소들을 탐색
for (int j=0;j<i;j++){
// i번째 원소가 j번째 원소보다 크고, i번째 dp가 j번째 dp값보다 작거나 같을경우
if (arr[i]>arr[j] && dp[i]<=dp[j]){
dp[i]=dp[j]+1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
// 최댓값(최대 길이) 탐색
int max =0;
for (int i : dp){
max = Math.max(max, i);
}
System.out.println(max);
}
}
문제 : https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
해당 문제는 수열 A 가 주어졌을때, 가장 긴 증가하는 부분 수열, LIS (Longest Increasing Subsequence) 의 길이를 구하는 문제이다.
다이나믹 프로그래밍에서 가장 중요한 것은 규칙을 찾거나, 일반식을 찾는 것이다.
먼저, arr[1] < arr[2] 이므로 dp[2] = dp[1] +1 을 대입한다.
1 | 2 | |
arr[i] | 10 | 20 |
dp[i] | 1 | 2 |
1 | 2 | 3 | |
arr[i] | 10 | 20 | 10 |
dp[i] | 1 | 2 | 1 |
arr[4]는 arr[2]보다 값도 크고, dp값도 2보다 작은 1이었으므로 dp[2] 값인 2에서 +1 해서 3을 넣는다.
1 | 2 | 3 | 4 | |
arr[i] | 10 | 20 | 10 | 30 |
dp[i] | 1 | 2 | 1 | 3 |
arr[5]도 같은 방법으로 진행한다.
1 | 2 | 3 | 4 | 5 | |
arr[i] | 10 | 20 | 10 | 30 | 20 |
dp[i] | 1 | 2 | 1 | 3 | 2 |
6번째까지 진행하면, dp값이 4가 최대임을 알 수 있다.
1 | 2 | 3 | 4 | 5 | 6 | |
arr[i] | 10 | 20 | 10 | 30 | 20 | 50 |
dp[i] | 1 | 2 | 1 | 3 | 2 | 4 |
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int [] arr = new int[N+1];
int [] dp = new int[N+1];
int cnt=1;
for (int i=0;i<N;i++){
arr[i]=sc.nextInt();
dp[i]=1;
}
for (int i=1;i<N;i++){
// 0 ~ i 이전 원소들을 탐색
for (int j=0;j<i;j++){
// i번째 원소가 j번째 원소보다 크고, i번째 dp가 j번째 dp값보다 작거나 같을경우
if (arr[i]>arr[j] && dp[i]<=dp[j]){
dp[i]=dp[j]+1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
// 최댓값(최대 길이) 탐색
int max =0;
for (int i : dp){
max = Math.max(max, i);
}
System.out.println(max);
}
}