BOJ#2532 먹이사슬 (Chain)

BOJ#2532 먹이사슬 (Chain)

* 문제

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

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2012 > 중등부 3번

* 풀이

Tip #1) 공식 풀이는 한국정보올림피아드 홈페이지에서 볼 수 있습니다.

Tip #2) 더블릿(http://www.dovelet.com)에서 채점하면 테스트케이스를 볼 수 있습니다.

Tip #3) LIS 문제입니다. LIS 관련해서는 아래 문제들을 먼저 풀어보는 것을 추천드립니다.

-가장 긴 증가하는 부분 수열 (https://www.acmicpc.net/problem/11053)

-전깃줄 (https://www.acmicpc.net/problem/2565)

이 문제의 입력값 중 동물의 번호는 필요가 없습니다.

동물의 활동영역 왼쪽/오른쪽 위치를 왼쪽 위치의 오름차순으로 정렬해보면,

1 5

2 4

3 4

5 7

6 10

7 8

9 10

그림으로 그려보면,

위 그림에서 볼 수 있듯이, 먹이사슬 구조를 갖는다는 것은 선이 겹친다는 것과 동일한 의미임을 알 수 있습니다.

결국 최대한 선이 많이 겹쳐진 수를 구하면 되는 것입니다.

즉,

1. 왼쪽 영역을 기준으로 오름차순으로 정렬한 후

2. 오른쪽 영역 숫자들을 가지고 '가장 긴 감소하는 부분 수열'의 길이를 구하면 되겠습니다.

3. 양 끝 구간이 같은 경우는 제외해야 한다.

4. 감소 수열에는 같은 숫자들이 들어갈 수 있다. -> binarySearch 시 추가 작업 필요.

예를 들어, [9 8 8 8 ..... 8 8 8 6 4] 수열에서 8을 찾는다면 ?

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232532_FoodChain/src

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

/**
 * BOJ#2532 먹이사슬
 * https://www.acmicpc.net/problem/2532
 */

public class Main {

    public static void main(String[] args) throws IOException {

        int N;
        Animal[] list;

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        list = new Animal[N];

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            Integer.parseInt(st.nextToken());

            list[i] = new Animal(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // start 값을 기준으로 오름차순 정렬 + end 값을 기준으로 내림차순 정렬
        Arrays.sort(list);


        // solve
        System.out.println(solve(list, N));
    }

    // end 값을 이용하여 최장 길이 감소 수열 LDS 만들기
    static int solve(Animal[] list, int N) {

        Integer[] tailTable = new Integer[N];
        int lengthOfLIS;

        // 초기값
        tailTable[0] = list[0].end;
        lengthOfLIS = 1;

        // solve
        for (int i = 1; i < N; i++) {

            if (list[i].isEqual(list[i - 1])) {

                continue;
            }

            // 후보값이 LDS 처음 값보다 큰 경우
            if (list[i].end >= tailTable[0]) {

                tailTable[0] = list[i].end;
            }

            // 후보값이 LDS 마지막 값보다 작은 경우
            else if (list[i].end <= tailTable[lengthOfLIS - 1]) {

                tailTable[lengthOfLIS++] = list[i].end;
            }

            // 후보값이 LDS 처음 값보다 작고, LDS 마지막 값보다 큰 경우
            else {

                // 1. 찾는 값이 없는 경우 -> 넣어야 할 자리를 return
                // 예) [9 8 8 8 6 4 2] 에서 7을 찾으면 4가 return 된다
                int idx = Arrays.binarySearch(tailTable, 0, lengthOfLIS, list[i].end, Comparator.reverseOrder());

                idx = idx < 0 ? -idx - 1 : idx;

                // 2. 찾는 값이 있는 경우 + 여러 개 있는 경우
                // 예) [9 8 8 8 8 ....8 7] 에서 8을 binarySearh로 찾으면 어떤 idx가 나올지 모른다.
                while (tailTable[idx] == list[i].end) {

                    idx++;
                }

                tailTable[idx] = list[i].end;
            }
        }

        return lengthOfLIS;
    }

} // main

class Animal implements Comparable {

    int start;
    int end;

    Animal(int start, int end) {

        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Object o) {

        // start 값을 기준으로 오름차순 + end 값을 기준으로 내림차순
        return this.start < ((Animal) o).start ? -1 : this.start > ((Animal) o).start ? 1 : this.end > ((Animal) o).end ? -1 : 1;
    }

    @Override
    public String toString() {

        return "(" + start + ", " + end + ")";
    }

    boolean isEqual(Animal animal) {

        return this.start == animal.start && this.end == animal.end;
    }
}