JAVA/문제 풀이
[백준 / BOJ] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA
ahue
2023. 10. 10. 21:32
728x90
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
LIS
가장 긴 증가하는 부분 수열을 구하는 문제를 LIS라고 한다. Longest Increasing Subsequence의 약자로, 배열의 일부 원소를 골라서 만든 부분 수열 중 각 원소가 이전 값보다 크다는 조건을 만족하는 가장 긴 수열을 뜻한다.
이번 문제는 수열의 길이 N의 최댓값이 1,000이기 때문에 시간 복잡도에 관계 없이 이중 for문을 돌릴 수 있었다. num은 원소를 순서대로 저장해놓은 배열이고, len은 해당 원소까지의 가장 긴 증가하는 부분 수열의 크기를 저장한다. 따라서 현재 원소보다 작은 원소 중 가장 큰 len 값 + 1이 현재 원소가 포함된 가장 긴 증가하는 부분 수열의 크기이다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 시간 : 96ms
// 메모리 : 11904KB
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] num = new int[N + 1];
int[] len = new int[N + 1];
for (int i = 1; i <= N; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
int max = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < i; j++) {
if(num[j] >= num[i]) continue;
if(len[i] < len[j] + 1) len[i] = len[j] + 1;
}
if(max < len[i]) max = len[i];
}
System.out.println(max);
}
}
반응형