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