링크
https://www.acmicpc.net/problem/11053
문제 설명
정답률 37.982%
수열 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 ≤ Ai ≤ 1,000)
6
10 20 10 30 20 50
출력 예제
- 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
4
풀이
주어진 수열에서 오름차순으로 구성가능한 원소들을 선택하여 최대 길이를 찾아내는 문제이다. 이는 최장 증가 수열 (LIS, Longest Increasing Subsequence)이라고 한다.
예제에서 입력값으로 주어진 수열에서 각 원소의 LIS를 구하면 다음과 같다.
수열의 각 원소를 탐색하면서 이전 원소들 중 작은 원소에 대해 재귀를 호출한다. 기본적으로 수열의 최소 길이는 1이다. 4번 인덱스인 20의 경우 더 작은 원소는 0번과 2번 인덱스인 10이다. 0번과 2번을 탐색할 때 재귀를 호출하여 10의 부분 수열의 길이를 반환받는데 10의 부분 수열의 길이는 1이므로 20의 부분 수열의 길이는 1을 더한 값인 2가 된다.
코드
//백준
public class Main {
static int[] seq;
static Integer[] dp;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
seq = new int[N]; //전체 수열
dp = new Integer[N]; //부분 수열의 길이를 담을 배열
//입력값 초기화
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
//모든 값에 대해 부분 수열 탐색
for (int i = 0; i < N; i++) {
LIS(i);
}
//부분 수열의 길이의 최대값
int max = Arrays.stream(dp)
.mapToInt(Integer::intValue)
.max()
.orElseThrow();
System.out.println(max);
}
static int LIS(int index) {
//탐색하지 않은 인덱스일 경우
if (dp[index] == null) {
dp[index] = 1; //부분 수열의 최소 길이 1
//seq[index]의 이전 노드 탐색
for (int i = index - 1; i >= 0; i--) {
//현재 노드보다 작은 값일 경우
if (seq[i] < seq[index]) {
dp[index] = Math.max(dp[index], LIS(i) + 1);
}
}
}
return dp[index];
}
}참고
백엔드