파이문

11053. 가장 긴 증가하는 부분 수열 본문

문제 풀이/BOJ

11053. 가장 긴 증가하는 부분 수열

민Z 2017. 11. 12. 18:43
728x90

11053. 가장 긴 증가하는 부분 수열

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



유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS)


일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 


가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다.


동영상 설명이 잘 되어 있어서 링크를 건다. https://www.youtube.com/watch?v=CE2b_-XfVDk

import java.util.Scanner;

public class Main {

    public int problem11053(int[] arr) {
        int[] dp = new int[arr.length];

        for (int i = 0; i < arr.length; ++i) {
            dp[i] = 1;
        }

        for (int i = 1; i < arr.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        int res = 1;
        for (int i = 0; i < arr.length; ++i) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        System.out.println(main.problem11053(arr));
    }
}


'문제 풀이 > BOJ' 카테고리의 다른 글

2293. 동전 1  (0) 2017.11.12
2579. 계단 오르기  (0) 2017.11.12
1149. RGB 거리  (0) 2017.04.04
1463. 1로 만들기  (0) 2017.04.03
1003. 피보나치 함수  (0) 2017.04.03
Comments