[백준 11722번] 가장 긴 감소하는 부분 수열 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 문제를 풀었습니다.

 

이번 문제의 목적인 가장 긴 감소하는 부분 수열을 구하는 것이므로 부분 수열의 최대 길이를 DP에 메모라이즈 하여 문제를 풀 수 있습니다.

 

만약 입력으로 N = 1, 입력 수로 10이 주어 지면 DP[0] = 1이고 정답 또한 1이 될 것입니다.

 

이번에는 N = 2, 입력 수로 10, 30이면 어떻게 될까요?

 

먼저 N이 어떤 수가 입력으로 주어지더라도 DP[0]은 무조건 1일 될 것입니다.

 

최초의 수는 시작하는 수이므로 길이가 1이 되기 때문입니다.

 

그럼 DP[1]은 어떻게 구해야 될까요?

 

감소하는 부분 수열을 구하는 것이므로 현재 수보다 이전(왼쪽의 수) 수가 더 큰 수를 찾아야 됩니다.

 

현재수가 30이므로 30보다 큰 수가 왼쪽에 있는지 확인해 보면 10만 있으므로 더 큰 수가 없습니다.

 

그러므로 DP[1]은 1이 됩니다.

 

예제를 위 과정으로 진행해 보겠습니다.

 

먼저 최초의 수는 길이가 1이므로 DP[0] = 1이 됩니다.

1

0

0

0

0

0

 

2번째 수인 30을 확인하면 이전 수가 10만 있으므로 DP[1] = 1이 됩니다.

10, 30 수열에서 {10} 또는 {30}이 감소하는 가장 긴 부분 수열이 됩니다.

1

1

0

0

0

0

 

3번째 수인 10을 확인하면 이전 수는 10과 30이 있습니다. 이전 부분 수열의 최대 길이는 1입니다.

 

이전 부분 수열의 최대 길이가 1이므로 10이 추가되면서 최대 길이는 2가 될 수 있습니다.

10, 30, 10 수열에서 {30, 10}이 감소하는 가장 긴 부분 수열이 됩니다.

1

1

2

0

0

0

 

4번째 수인 20을 확인하면 이전 수는 10, 30, 10이 있습니다. 이전 수들 중 20보다 큰 수는 30이 있습니다. 부분 수열의 길이 또한 1이므로 20이 추가 되면서 최대 길이는 2가 될 수 있습니다.

10, 30, 10, 20 수열에서 {30, 20}이 감소하는 가장 긴 부분 수열이 됩니다.

1

1

2

2

0

0

 

5번째 수 또한 위 과정으로 최대 길이는 2가 됩니다.

1

1

2

2

2

0

 

6번째 수인 10을 확인하면 이전 수는 10, 30, 10, 20, 20이 있습니다. 이전 수들 중 10보다 큰 수는 30, 20, 20이 있습니다.

이전 수들의 길이 중 최대 값은 2이므로 10이 추가 되면서 최대 길이는 3이 될 수 있습니다.

10, 30, 10, 20, 20, 10 수열에서 {30, 20, 10}이 감소하는 가장 긴 부분 수열이 됩니다.

1

1

2

2

2

3

 

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTokenizer;

int num = Integer.parseInt(br.readLine());
stringTokenizer = new StringTokenizer(br.readLine());

int[] arr = new int[num];
int[] dp = new int[num];

dp[0] = 1;

for(int i=0; i<num; i++)
	arr[i] = Integer.parseInt(stringTokenizer.nextToken());

for(int i=1; i<num; i++){
	int max = 0;
	for(int j=0; j<i; j++){
		if(arr[i] < arr[j])
			max = Math.max(dp[j], max);
	}
	dp[i] = max + 1;
}

Arrays.sort(dp);

bw.write(dp[num-1]+ "\n");
bw.flush();