티스토리 뷰
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 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- java
- js array
- BOJ
- 프로그래머스 SQL
- JS 딥다이브
- 백기선 스터디
- 이펙티브자바 아이템60
- JPA 연관관계 매핑
- REST API
- dreamcoding
- ㅇㄷㅇㅈ
- 드림코딩
- 이펙티브자바 스터디
- HTTP 완벽 가이드
- 모던자바스크립트
- GCP
- 백준
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- js promise
- 프로그래머스
- 킹수빈닷컴
- 이펙티브자바 아이템59
- 이펙티브자바
- HTTP 완벽가이드
- 김영한 http
- Spring Security
- http
- js api
- 패스트캠퍼스 컴퓨터공학 완주반
- 김영한 JPA
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함