Baekjoon11053: 가장 긴 증가하는 부분 수열, 3가지 풀이

가장 긴 증가하는 부분 수열

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

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이1

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

 

[ 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<N ; i++) {
				if(dp[i][0]<dp[N][0]) {
					min = false; //한번이라도 작은값이 있으면 최소값이 아니다
					max = Math.max(increase(i)[1], max);
		//자신보다 작고 왼쪽에 있는 값들에 대해서 최대값을 가져옴
				}
				out=Math.max(increase(i)[2], out);
			}
			if(min) { 
				dp[N][1]=1; //최소값인 경우 본인은 1을 가짐
			} else {
				dp[N][1]=max+1;
        //최소값이 아닌 경우 왼쪽 값의 최대값을 더함
			}
			if(out<=dp[N][1]) {
				dp[N][2]=dp[N][1];
			} else dp[N][2]=out;
	   }
		
		return dp[N];
	}
public static void main(String[] args){
	 Scanner sc = new Scanner(System.in);
	 int N = sc.nextInt();
	 dp = new Integer[N][3];
     //0은 숫자, 1은 그 항이 가지는 값, 2는 그 때까지의 최대값
	 dp[0][1]=1;
	 dp[0][2]=1;
	 for(int i=0; i<N;i++) {
		 dp[i][0]=sc.nextInt();
	 }
	 System.out.print(increase(N-1)[2]);
}}

 

풀이2

반복문을 이용하여 풀이한다. 증가하는 순열이기에 같이 증가하는 반복문을 사용하면 더 효율적이다

모든 값을 배열에 넣었다고 가정한다. dp[N]값에는 기본값으로 1이 주어진다.

1) 1번항보다 오른쪽에 있는 수 중 1번항보다 큰 모든 수에 1을 더한다.

2) 2번항의 경우

        i) 2번항보다 오른쪽에 있는 값들과 비교한다. (2번항 vs 탐색항)

       ii) 2번항보다 탐색항이 큰 숫자인 경우 2번항 + 1 을 한 값과 현재 탐색항이 가지고 있는 값과 비교해 큰 값을 넣는다

3) n항의 경우

        i) n번항보다 오른쪽에 있는 값들과 비교한다

       ii) 탐색항이 n번항보다 큰 숫자인 경우 n번항+1을 한 값과 탐색항의 값을 비교해 더 큰 값을 넣는다

 

이중배열 + 다음 항

import java.util.*;
public class Main {
public static void main(String[] args){
	 Scanner sc = new Scanner(System.in);
	 int N = sc.nextInt();
	 int[][]dp=new int[N][2]; //효율을 위한 이중배열 사용
	 int max=0;
	 for(int i=0; i<N;i++)dp[i][0]=sc.nextInt(); //값을 집어넣기
	 for(int i=0; i<N;i++){
		 for(int j=i; j<N; j++) {
			 if(dp[j][0]>dp[i][0])dp[j][1]=Math.max(dp[i][1]+1, dp[j][1]);
             //i보다 j항이 큰 수를 가질 경우: i+1과 현재 j가 가지고 있는 값 중 큰 값을 넣어줌
			 max=Math.max(dp[j][1],max);}}
	 System.out.print(max+1);
}}

풀이3

코드를 더 짧게 만들기 위해 값을 넣어주며 탐색한다.

새로 값을 넣어주고 현재까지의 항들과 비교해 새로운 값이 더 큰 값이면 지금 가지고 있는 값과 이전항 값의+1을 비교해 더 큰 수를 넣는다.

 

이중배열 + 이전 항

import java.util.*;
public class Main {
public static void main(String[] args){
	 Scanner sc = new Scanner(System.in);
	 int N = sc.nextInt();
	 int[][]dp=new int[N][2];
	 int max=0;
	 for(int i=0; i<N;i++) {
		 dp[i][0]=sc.nextInt();
		 for(int j=0; j<=i; j++) {
			 if(dp[j][0]<dp[i][0])dp[i][1]=Math.max(dp[j][1]+1, dp[i][1]);
			 max=Math.max(dp[i][1],max);}}
	 System.out.print(max+1);
}}