백준 11053번 가장 긴 증가하는 부분수열 (java)

[Silver II] 가장 긴 증가하는 부분 수열 - 11053

문제 링크

성능 요약

메모리: 15352 KB, 시간: 124 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 8월 27일 17:38:13

문제 설명

수열 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)

출력

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

풀이

LIS 알고리즘을 활용하여 풀이했다.

 

이중 포문으로 바깥 포문은 한 바퀴를, i=0, i<N

 

내부 포문은 바깥 포문 부터 끝까지를 돌면서 j = i+1, j <N

 

만약 배열[i] < 배열[j] 라면 자기보다 크다는 얘기니까 증가하는 부분 수열이라 여길 수 있다,

 

그러므로 dp 배열을 따로 만들어 dp의 값을 1 더해주는 방식으로 풀이하면 된다.

 

여기서 dp의 값을 무작정 증가시키는 것이 아닌,

 

dp[j] = Math.max(dp[i]+1, dp[j])를 비교해야 한다.

 

dp[i] 에서 +1 한 값이 무조건 더 크다는 것을 보장할 수 없기 때문이다.

 

전체 코드

public class Main {
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int x[] = new int[N];
        int dp[] = new int[N];

        for(int i = 0 ;i<N;i++){
            x[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        int max = 1;

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

        bw.write("" + max);
        bw.flush();
    }
}