Baekjoon11053: 가장 긴 증가하는 부분 수열

Baekjoon11053: 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초 256 MB 84740 32987 21636 37.047%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

재귀함수를 사용해서 풀이할 것인데, [ 작은 숫자 → 큰 숫자 ] 의 개념을 [ 큰 숫자 → 작은 숫자 ] 탐색으로 생각해본다.

[ 10, 20, 10, 30 ]으로 먼저 축소해서 생각해본다

30은 왼쪽에 10과 20을 선택할 수 있다

첫번째 경우: 10보다 작은 수가 없기에 2가 된다

두번째 경우: 20을 선택하면 더 작은 수 10이 존재하기에 길이가 3이 될 수 있다.

[ 10, 20, 10, 30, 20, 50]

50인 위치에 있을 때, 자기보다 왼쪽에 있고 작은 수 중에 최대값 하나를 선택하고 1을 더해 가져온다.

최대값을 가지는 항은 → 4항(30)=3이다

30은 자기보다 왼쪽에 있고 작은 수 중 최대값 하나를 선택하고 1을 더해 가져온다.

최대값을 가지는 항은 → 2항(30)=2이다

20은 자기보다 왼쪽에 있고 작은 수 중 최대값 하나를 선택하고 1을 더해 가져온다.

최대값을 가지는 항은 → 1항(10)=1이다

10은 자기보다 왼쪽에 작은 수가 없으므로 1을 반환한다

자신보다 작은 수가 있고 그 중에서 최대값을 더하는 작업을 했다

그 중에서 최대값만을 출력해야하는데 현존 최대값을 기록하기 위해 배열의 공간을 하나 더 사용한다

반복문 안에서 지금까지의 값 중 최대값만을 가져와 배열에 넣는다

배열의 크기는 [N][3]이 된다. 입력받는 N값의 크기와 [해당 숫자][자기보다 작은 수 중 최대값+1][현존 최대값]

각각 dp[N][0], dp[N][1], dp[N][2]에 들어간다. 반복문을 이용해 각각의 값을 구할 수 있다.

dp[N][0]: 값을 비교할 숫자들

dp[N][1]: ( 지금 항보다 작은 항 ) + [해당 숫자]가 더 작은 값 중 최대값을 구하고 1을 더해 집어넣은 값

dp[N][2]: 현재까지 구한 dp[N][1] 중 최대값을 저장

import java.util.*; public class Main { static Integer[][] dp; static Integer[] increase(int N) { if(dp[N][1]==null || dp[N][2]==null ) { int max = 0; int out =0; boolean min = true; for(int i=0; i

from http://devyoseph.tistory.com/110 by ccl(A) rewrite - 2021-10-26 06:28:37