2019-03-21 [JAVA]백준 11053 - 가장 긴 증가하는 부분 수열
22 Mar 2019 | java algorithm_study문제출처
https://www.acmicpc.net/problem/11053
풀이
dp => 최대 수열 개수
| num | 10 | 20 | 10 | 30 | 20 | 50 |
|---|---|---|---|---|---|---|
| Dp | 1 | 2 | 1 | 3 | 2 | 4 |
- dp[n]은 n-1까지 수들 중 num[n]보다 작은 값에서 최대 dp+1
- num[n]보다 작은 값이 없을 때 dp[n] = 1
- 출력은 dp중 가장 큰 값
for (int i=2; i<=n; i++){
for (int j=1; j<i; j++){
if(num[i]>num[j])
dp[i] = Math.max(dp[i], dp[j]+1);
else
dp[i] = Math.max(dp[i], 1);
}
}
전체소스
import java.util.Scanner;
public class Baekjoon_11053 {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
int[] num = new int[n+1];
int[] dp = new int[n+1];
for(int i=1; i<=n;i++)
num[i] =sc.nextInt();
dp[1] = 1;
for (int i=2; i<=n; i++){
for (int j=1; j<i; j++){
if(num[i]>num[j])
dp[i] = Math.max(dp[i], dp[j]+1);
else
dp[i] = Math.max(dp[i], 1);
}
}
int max = 0;
for(int i=1; i<=n; i++)
max = Math.max(max, dp[i]);
System.out.println(max);
}
}
Comments