boj)11053 - 가장 긴 증가하는 부분 수열
2020. 9. 17. 21:38ㆍPS/boj
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class boj_11053 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n+1];
int[] dp = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
int max = 0;
for (int j = 1; j <= n-1; j++) {
if (arr[j] < arr[i] && dp[j] > max) {
max = dp[j];
}
}
dp[i] = max + 1;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dp[i] > ans) {
ans = dp[i];
}
}
System.out.println(ans);
}
}
- 앞에서부터 dp테이블 한 칸씩 접근
- 수열의 인덱스를 기준으로 봤을때 앞에 인덱스의 값이 나보다 작으면 연결할 수 있다고 봄
- 점화식 dp[n] = dp[j] + 1; 로 볼 수 있다.
- j의 조건은 1 ~ n-1 까지의 인덱스, arr[j] < arr[i] 이다.
'PS > boj' 카테고리의 다른 글
boj)1912 - 연속합 (0) | 2020.09.18 |
---|---|
boj)14002 - 가장 긴 증가하는 부분 수열 4 (0) | 2020.09.18 |
boj)2193 - 이친수 (0) | 2020.09.17 |
boj)10844 - 쉬운 계단 수 (0) | 2020.09.17 |
boj)15590 - 1, 2, 3 더하기 5 (0) | 2020.09.17 |