boj)14002 - 가장 긴 증가하는 부분 수열 4
2020. 9. 18. 00:53ㆍPS/boj
import java.util.Scanner;
public class boj_14002 {
static int[] arr;
static int[] dp;
static int[] v;
// 출력 함수
static void print(int p) {
if (p == 0) return;
print(v[p]);
System.out.print(arr[p] + " ");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n+1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
dp = new int[n+1]; // dp
v = new int[n+1]; // 역추적
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i] && dp[i] < dp[j]+1) {
dp[i] = dp[j] + 1;
v[i] = j; // 찾아간 값의 index를 배열에 저장
}
}
}
int ans = 0;
int index = 0;
for (int i = 1; i <= n; i++) {
if (ans < dp[i]) {
ans = dp[i];
index = i; // ans의 index 뽑기
}
}
System.out.println(ans);
print(index); // ans의 index부터 재귀 시작
System.out.println();
}
}
- 증가하는 부분 수열과 비슷한데 역추적을 통해 지금까지 값들을 찾아가야함
- 나의 바로 앞에 있는 값의 인덱스를 v[] 배열에 저장
- 나의 값이 다음 값을 불러오는 형태이니까 재귀함수로 표현
- ans를 뽑을때 index로 부터 print 시작
'PS > boj' 카테고리의 다른 글
boj)1699 - 제곱수 (0) | 2020.09.18 |
---|---|
boj)1912 - 연속합 (0) | 2020.09.18 |
boj)11053 - 가장 긴 증가하는 부분 수열 (0) | 2020.09.17 |
boj)2193 - 이친수 (0) | 2020.09.17 |
boj)10844 - 쉬운 계단 수 (0) | 2020.09.17 |