[JAVA / 자바] 백준(BOJ) 11053번 - 가장 긴 증가하는 부분 수열 (실버 2)

 문제 

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

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

---

 입력 

 

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

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

---

 출력 

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

---

 

---

 문제 접근 방법 

이번 문제는 다이나믹 프로그래밍(Dynamic Programming)으로 풀 수 있는 문제이다.

두 번째 줄에 수열을 입력받아 arr [] 배열에 저장한다.

입력을 저장한 arr배열을 순회하면서 현재 인덱스(idx)의 이전 인덱스(0 ~ idx-1)에 저장된 수와 비교하여 현재 인덱스(idx)에 저장된 수가 더 큰 경우 dp배열에서 dp [idx]에 저장된 값과 dp [이전 인덱스]+1 값 중 더 큰 값을 dp [idx]에 저장해 경신해준다. => Math.max(dp [idx], dp [현재 인덱스에 저장된 값보다 작은 값이 저장된 이전 인덱스]+1)

arr배열 순회가 끝나면 dp배열을 순회하여 저장되어 있는 가장 큰 수를 찾아 해당 수에 +1 한 값을 출력해주면 된다.

(+1의 이유는 수열의 시작은 카운팅이 안되었기 때문이다.)

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 입력되는 숫자의 양이 적어서 위와 같은 코드로도 풀 수 있었지만, 앞으로 나오는 증가수열 문제에서는 입력되는 숫자의 양과 범위가 훨씬 넓어지기 때문에 보다 성능을 끌어올려야 한다. 각 상황에 맞는 코드를 리뷰할 예정이니 어떤 차이가 있는지 비교해보는 것도 좋을 것 같다.

---

 문제 원본 

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

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

 

 알고리즘 분류 

• 다이나믹 프로그래밍