가장 긴 증가하는 부분 수열 5(백준_14003)

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

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

 

문제 설명

문제는 간단하다. 수열이 주어지면 가장 긴 증가하는 부분 수열을 찾으면 된다.

예시 처럼 10 20 10 30 20 50이 주어지면 10 20 30 50이 가장 길다.

 

문제에 대한 아이디어

제일 처음 생각해본 아이디어는 무작정 sort해서 겹치는 것을 빼면 안될까? 라고 생각했지만 이 문제는 2가지의 순서가 존재했다. 현재 수열들 수 자체의 순서와 index의 순서도 고려해줘야 한다. 그래서 간단한 방식으로 해결할 수는 없다. 역시 플레5 문제

 

다이나믹 프로그래밍 이용하기!!(Do it 알고리즘 코딩 테스트 참고)

이 문제는 점화식을 이용해서 풀어야 한다. 총 3가지 배열을 준비해야 한다.

• a[] : 문제의 수열을 받는 배열
• b[] : 현재 index에서 제일 작은 수
• d[] : 각 수열의 번호

이렇게 말하면 어려우니 그림으로 설명하겠다.

 

최장 부분 수열의 길이 구하기

위의 표가 처음 초기 상태이다.

이후 2번째 5와 B[]에서 제일 마지막 숫자와 비교한다. 만약 더 크면 D[] + 1을 하면 된다. 하지만 작다면 B[]에서 5가 몇번째 index여야 하는지 찾아야한다. 여기서는 5가 1번 index여야 하므로 11이 5로 바뀐다.

이후 똑같이 진행을 한다.

7은 지금 b[]의 마지막 index인 12보다 작다. 그러므로 D[] + 1이 불가능하고 B[]에서 7은 몇번째 index인지 찾아야 한다. 7은 5보다 크고 10보다 작으므로 2번 index여야 한다. 그리고 D[]는 현재 B[]의 index 번호가 들어간다.

여기서 index를 찾을 때 그냥 찾으면 시간초과가 나온다. 그러므로 binarySearch로 찾아야한다.

이 알고리즘을 반복하면

최종 결과를 얻게 된다. 지금 최장 증가 부분 수열의 길이는 5가 되는 것이다. 

하지만 최장 증가 부분 수열이 B[]인 것은 아니다. 왜냐하면 B[]는 A[]의 index 순서는 신경쓰지 않았기 때문이다.

이제 최장 증가 부분 수열 자체를 알아내야 한다.

 

최장 부분 수열 구하기

지금 우리는 최장 부분 수열의 크기를 알고 있다. 그러므로 간단하게 a[]의 마지막 부터 최장 부분 수열의 크기와 d[]가 같은 것을 찾아가면 된다.

• 최장 부분 수열의 크기는 5, a의 뒤에서 부터 탐색 결과 24가 5임, 크기 하나 줄임 = 4
• 지금 크기는 4, d[]의 값이 4이고, a[] 의 값이 24보다 작은 것을 찾아야함.
• 이걸 계속 반복

결국 5 10 12 14 24의 결과를 알수있다 !!

 

구현

• 필요한 내용

static int maxLength;
static int []a; //받은 수열
static int []b; //현재 index 숫자 저장
static int []d; //몇번째인지 저장
static int ans[];

• binarySearch

public static int binarySearch(int l, int r, int now){
    int mid;
    while(l < r){
        mid = (l+r)/2;
        if(b[mid] < now){
            l = mid+1;
        }
        else r = mid;
    }
    return l;
}

• Main

public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    int n = Integer.parseInt(st.nextToken());
    a = new int[1000001];
    b = new int[1000001];
    d = new int[1000001];
    ans = new int[1000001];
    st = new StringTokenizer(buf.readLine());
    for(int i =1; i<=n; ++i){
        a[i] = Integer.parseInt(st.nextToken());
    }
    int index = 0;
    b[++maxLength] = a[1];
    d[1] = 1;
    for(int i =2; i<=n; ++i){
        //제일 마지막 요소보다 크면
        if(b[maxLength] < a[i]){
            b[++maxLength] = a[i];
            d[i] = maxLength;
        }else{
        //작으면 몇번째 요소인지 찾아야함
            index =binarySearch(1,maxLength,a[i]);
            b[index] = a[i];
            d[i] = index;
        }
    }
    System.out.println(maxLength);
    index = maxLength;
    int x = b[maxLength]+1;
    //최장 증가 부분 수열 찾기
    for(int i = n; i >= 1; --i){
        if(d[i] == index && a[i] < x){
            ans[index] = a[i];
            x = a[i];
            --index;
        }
    }
    for(int i = 1; i<=maxLength; ++i){
        System.out.print(ans[i] + " ");
    }

}

 

https://github.com/Heron-Woong/CodingTest_Practice/commit/974d83bcbe4eb9f3e903648a26ea8193da456202

백준_14003, 가장 긴 증가하는 부분 수열 5 · Heron-Woong/CodingTest_Practice@974d83b