[백준]동적 계획법1/가장 긴 증가하는 부분 수열/11053 풀이 JAVA

문제

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

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

A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

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

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

 

출력

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

 

 

풀이(JAVA)

예제를 보면서 문제를 이해해 보자.(백준 예제)

아래와 같은 수열 A와 부분 수열의 길이인 dp 배열이 있다.

index	0	1	2	3	4	5
A	10	20	10	30	20	50
dp	1	2	1	3	2	4
부분 수열	{10}	{10, 20}	{10}	{10, 20, 30}	{10, 20}	{10, 20, 30, 40}

dp[N]에 dp[0]부터 dp[N]까지 오름차순인 요소들의 갯수를 저장하는 방법이다.

 

다른 예제 하나 더

index	0	1	2	3
A	30	20	10	20
dp	1	1	1	2
부분 수열	{30}	{20}	{10}	{10, 20}

---

여기부터는 내가 삽질한 부분이다.

 

궁금증 1

수열 A가 {3, 2, 1, 2}면

최대 증가 부분 수열은 {1, 2}의 2이다!

(dp는 {1, 1, 1, 2}가 된다.)

나는... {1, 2, 3}해서 3일 줄 알았는데

dp[0]부터 dp[N]까지 증가 부분 수열을 구해야하기 때문에 A[N]이상의 요소를 포함할 수 없다~~

 

그리고 위의 예제인 A = {10, 20, 10, 30, 20, 50}만 보고

오잉? 걍 for문 돌려서 큰 거 만나면 count++하는 식으로 한 담에 count 출력하면 되는 거 아냐?

이렇게...^^

int max = A[0]; 
int count = 1;
for (int i = 1; i < N; i++)
	if (max < A[i]) {
    		max = A[i];
        	count++;
        }

 

라고 생각했다가~ 틀렸다.

왜 틀렸냐면...

A={4, 1, 2, 3}같은 수열로 예를 들 수 있는데,

이때 dp는 {1, 1, 2, 3}이 된다.

그런데 저 코드대로 하면

max = 4가 되어서 count가 더이상 ++이 될 수 없다.

 

궁금증 2

dp[N] = Math.max(dp[N], LTS(i) + 1);을

dp[N] = LTS(i) + 1;이라고 해도 되지 않을까!? 였는데... 역시 안 된다.

dp[N] = LTS(i) + 1;라고 하면

A = {1, 2, 3, 2}에서

dp = {1, 2, 3, 1}이 되어야하는데,

LTS(2)떄 dp[2] = LTS(1) + 1 = 2가 되어버린다. 3이 되어야 하는데!!

(dp = {1, 2, 2, 2}가 되어버린다.)

그래서 꼭 현재 값보다 작아지지 않도록... 비교를 해주어야 한다.

 

궁금증 3

LTS(0 ~ N - 1)을 for문으로 돌리지 말고 어차피 재귀니까 LTS(N - 1)로 하면 안될까!?

안 된다!

A = {1, 2, 3, 1}을 예제로 들 수 있다.

dp = {1, 2, 3, 1}이 되어야하지만

dp = {0, 0, 0, 1}이 되어버린다.

왜냐하면 LTS(3)으로 시작하지만, A[3]보다 작은 것은 없기에 if문 안의 LTS재귀를 할 수가 없다!

 

참 많이도 궁금했지만 해결해서 기분이 좋다. 허리는 좀 아프지만....^^