[BaekJoon] 백준 11053번_가장 긴 증가하는 부분 수열 for JAVA

 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

 

 

---

 

 

방심했다가 여러번 틀린 문제이다.

 

 

일단 부분수열..이라고 했지만 N의 크기가 1,000까지이기 때문에 부분집합을 이용하면 큰일난다는 직감이 온다.

 

 

그렇다면 for문을 사용해서 훑어야할 것 같다!

 

그래서 처음에는 1000 x 1000 = 1,000,000 이므로 2중 for문을 이용해서 앞에꺼보다 뒤에꺼가 크면 cnt+1 해주는 식으로 진행하였고

 

 

당연히 틀렸다!!

 

 

 

틀린 코드(안봐도 됨)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A[] = new int[N];
		for(int i=0; i<N; i++)
			A[i] = Integer.parseInt(st.nextToken());
		
		// 입력 끝
		int answer = 0;
		for(int i=0; i<N-1; i++) {
			int count = 1;
			int tmp = A[i];
			for(int j=i+1; j<N; j++) {
				if(A[j] > tmp) {
					count += 1;
					tmp = A[j];
				}
			}
			if(answer < count) answer = count;
		}
		
		System.out.println(answer);

	}

}

 

 

 

 

생각해보니 저렇게 짜면 수열 A = {10, 20, 50, 40, 20, 50} 인 경우

 

10 -> 20 -> 40 -> 50 이어야하는데 

10 -> 20 -> 50 이 되어버린다.

 

 

그렇게 조금 고민해봤는데,, 회의실 문제처럼 dp를 사용하기로 하였다.

 

 

앞에서부터 훑으면서 그 자리에서 나올 수 있는 증가한 개수 중 가장 큰 수를 저장하기로 했음.

 

 

무슨 말인지 그림을 통해 살펴보자^^

 

 

 

위 그림처럼 dp배열을 만들 것이다.

 

첫번째 수에서는 10밖에 없으므로 거기서 멈춘다고 생각하면 1만 들어올 수 있다.

 

 

 

 

 

다음 수열의 수는 20이다.

 

그러면 앞의 수인 10보다 크므로 10 -> 20 이 가능하기 때문에 2가 된다.

 

 

 

 

 

다음은 10이다. 10보다 작은 수가 앞에 없기 때문에 그냥 1이다.

 

 

 

 

 

그 다음은 30임. 30보다 작은 수는 10,20,10 다 20보다 작다.

 

그중에서 dp가 가장 큰 값인 2에 1을 더해서 3이 된다.

 

10 -> 20 -> 30 이므로 3

 

 

 

 

그 다음은 20이다.

 

20보다 작은 수는 앞에 10이 있는데 둘 다 1이므로 2가 된다.

 

10 -> 20

 

 

 

 

그 다음은 50이다.

 

 

앞에 있는 숫자들 중 모든 숫자가 50보다 작다.

 

그러면 그중에서 dp에 있는 값이 제일 큰 3에 1을 더해서 4가 된다.

 

10 -> 20 -> 30 -> 50 이라서 4

 

 

---

 

이렇게 풀었다.

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A[] = new int[N];
		for(int i=0; i<N; i++)
			A[i] = Integer.parseInt(st.nextToken());
		
		// 입력 끝
		int dp[] = new int[N];
		dp[0] = 1;
		int answer = 1;
		
		for(int i = 1; i < N; i++) {
			int max = 1;
			for(int j=i-1; j>=0; j--) {
				if(A[j] < A[i] && max <= dp[j])
					max = dp[j] + 1;
			}
			dp[i] = max;
			if(max > answer) answer = max;
		}
		
		System.out.println(answer);

	}

}

 

 

 

성능