[백준 11053번] 가장 긴 증가하는 부분 수열 Java 풀이

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

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

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

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP를 이용하여 풀어보았습니다.

 

입력받은 수열의 길이가 1이라면 어떤 수여도 가장 긴 증가하는 부분 수열의 길이는 1이 될 것입니다.

 

그럼 입력받은 수열의 길이가 2개인 경우를 살펴보도록 하겠습니다.

 

아래 표와 같이 입력을 받은 경우 DP[0]은 어떤 수가 와도 1이므로 1이 되고 DP[1]의 경우 현재 수(20)의 이전 수인 10의 DP값에 1을 더한 값인 2가 됩니다.

10

20

 

이번에는 입력이 아래 표와 같은 경우 DP[0]은 1이 되고 DP[1]은 현재 수(10) 이전의 수인 20의 경우 현재 수(10) 보다 큰 수 이므로 증가하는 부분 수열이 될 수 없습니다. 하여 DP[1]또한 1이 되게 됩니다.

20

10

 

이번에는 입력받은 수열의 길이가 3인 경우를 살펴보도록 하겠습니다.

 

아래 표와 같이 입력을 받은 경우 DP[0]은 1이 되고 DP[1]의 경우는 현재 수(20)의 이전 수들 중 20보다 작은 10이 있으며 10의 Index의 DP값인 1에 1을 더한 2가 DP[1]의 값이 됩니다.

 

DP[2]의 경우 현재 수(30)의 이전 수들 중 20보다 작은 10과 20이 있으며 10과 20 중 Max는 20의 Index의 DP값인 2에 1을 더한 3이 DP[2]의 값이 됩니다.

10

20

30

 

아래 표와 같이 입력을 받은 경우 DP[0]은 1이 되고 DP[1]의 경우는 현재 수(10)의 이전 수들 중 10보다 작은 수가 없으므로 1이 DP[1]의 값이 됩니다.

 

DP[2]의 경우 현재 수(30)의 이전 수들 중 30보다 작은 10과 20이 있으며 10, 20 모두 DP의 값이 1이므로 1에 1을 더한 2가 DP[2]의 값이 됩니다.

20

10

30

 

마지막으로 만들어진 DP의 Max 값을 찾기 위해 DP 배열을 정렬하여 맨 마지막 위치의 값을 출력하였습니다.

 

만약 이번 문제를 풀이를 참고하여 풀었다면 이번 문제와 유사한 백준 11722번(가장 긴 감소하는 부분 수열)을 한번 도전해 보는 것도 좋을 것 같습니다.

6. 코드

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

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

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

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

for(int i=0; i<length; i++) {
	dp[i] = 1;
	arr[i] = Integer.parseInt(stringTokenizer.nextToken());

	for(int j=0; j<i; j++){
		if(arr[j] < arr[i] && dp[j] + 1 > dp[i])
			dp[i] = dp[j] + 1;
	}
}

Arrays.sort(dp);

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