[알고리즘] 백준 11053 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열

 

 

 

정말 알것 같다 싶으면 새로운 유형이 나와버리는 동적프로그래밍이다! 조금씩 익숙해지고는 있지만 자잘한 조건에 난감한 경우가 많다. 

 

이 문제는 LIS문제이다. 이걸 처음 접하면 이게 왜 동적 프로그래밍 문제지? 하고 의문을 가지고 내 식대로 풀다가 망하는 경우가 100% 된다. 

 

망하는 이유는 문제를 정확히 이해하지 못했기 때문이다. 아래는 문제에서 주어진 조건이다.

6
10 20 10 30 20 50

이렇게 보면 그냥 처음부터 max값을 찾아서 10 20 넣고 10은 건너뛰고 30넣고 20은 건너뛰고 50넣고.. 이렇게 하면 될것 같다. 

 

그래서 아래는 그렇게 짠 코드이다.

public class BaekJoon_16_11053_2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] A = new int[1001];
		
		A[0] = Integer.MIN_VALUE;
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		List<Integer> dp = new ArrayList<Integer>();
		dp.add(A[1]);
		int max = Integer.MIN_VALUE;
		for (int i = 2; i <= n; i++) {
			if (max < A[i]) {
				max = A[i];
				dp.add(A[i]);
			}
		}

		writer.write(dp.size() + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

근데 .. 이 코드의 문제점은 무조건 처음부터 시작해서 더 이상 큰값이 나오지 않으면 그걸로 끝인 코드이다. 그게 무슨말이냐면, 아래의 조건을 보자

10
1 5 2 1 4 3 4 5 2 1

이 조건을 기준으로 저 코드에 대입해보면 1다음에 5가 나오고 5이상으로 큰 값이 뒤에 없기 때문에 그대로 2가 출력된다. 하지만 이 문제는 최장길이를 구하는 문제이다. 왼쪽에서 가까이있는걸 푸는 문제가 아니다. 가장 길이가 긴 부분 수열을 찾는 것이다.

즉 2가아니고,

 

1 5 2 1 4 3 4 5 2 1, 즉 5가 된다. 

 

처음부터 max값으로 비교하는 문제가 아니라는 뜻이다. 처음에 문제를 정확히 이해하지 못하고 마구잡이로 풀었는데, 

그래서 최장 증가 수열 문제이다.

 

 

 

근데 그 원리만 정확히 알고나면 어려울 건 전혀 없다.. 그냥 하나의 로직이다.

 

아래는 구현 코드이다.

 

public class BaekJoon_16_11053 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] A = new int[1001];
		int[] dp = new int[1001];

		A[0] = Integer.MIN_VALUE;
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		dp[0] = 0;
		dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			dp[i] = 1; // 기준 최저인 1로 설정해두고 큰값나올때마다 수정
			for (int j = 1; j < i; j++) {
				if (A[i] > A[j])
					dp[i] = Math.max(dp[j] + 1, dp[i]); // 지금것보다 크면 계속 업데이트
			}
		}

		int max = Integer.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			if (max < dp[i])
				max = dp[i];
		}
		writer.write(max + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

 

화이또!