[Java] 백준 23035. 가톨릭대는 고양이를 사랑해

📌 문제 링크 - https://www.acmicpc.net/problem/23035

 

 

---

 

 

 

 

 

 

문제

가톨릭대학교에는 많은 고양이가 있다. 고양이를 사랑하는 많은 학생 중 한 명인 쿠기는 수업 시간보다 항상 일찍 등교해서 고양이 밥을 챙겨주곤 했다. 안타깝게도 이제 4학년이 된 쿠기는 취업 준비에 바빠 고양이를 챙기는 것에 많은 시간을 쏟을 수 없게 되었다.

그런데도 고양이를 사랑하는 쿠기는 학교 정문에서부터 수업이 있는 다솔관까지 가는 여러 경로 중에, 가장 많은 고양이를 만나 밥을 챙겨 줄 수 있는 경로를 찾고 싶어 한다. 쿠기는 다솔관까지 상, 하, 좌, 우 방향으로만 이동하며, 한 번 이동하는 시간은 1만큼 걸린다. 이때, 고양이에게 밥을 주는 시간은 무시할 수 있을 정도로 짧다. 쿠기는 정문에서 다솔관까지 가장 빠르게 움직일 때만 수업에 늦지 않을 수 있다. 마음 착한 쿠기가 수업에 늦지 않으면서 최대한 많은 고양이의 밥을 챙길 수 있도록 도와주자.

가톨릭대는 크기가 N × M인 직사각형이고, 정문은 (0, 0), 다솔관은 (N, M)에 있다.

 

 

입력

첫 번째 줄에 정수 N, M(0 ≤ N, M ≤ 1,000,000,000)이 주어진다.

두 번째 줄에 고양이의 수를 나타내는 정수 T(0 ≤ T ≤ 100,000)가 주어진다.

세 번째 줄부터 T개의 줄에 고양이의 위치를 나타내는 정수 r, c(0 ≤ r, c ≤ 1,000,000,000)가 주어진다. 두 개 이상의 좌표가 중복되는 경우는 없고, 가톨릭대 밖에 고양이가 존재할 수 있다.

 

 

 

출력

첫 번째 줄에 수업 시간 전에 밥을 챙겨줄 수 있는 고양이의 최대 마릿수를 출력한다.

 

 

 

 

 

 

---

 

 

풀이

LIS를 응용해서 풀 수 있는 문제다. 

 

가톨릭대 밖에 고양이가 존재할 수 있으므로 가톨릭대 크기인 N이나 M 이내의 위치만 리스트에 저장하였다.

입력을 받은 후 정렬을 해주면 되는데, 수업에 늦지 않기 위해 최소한의 이동으로 이동하면서 고양이의 밥을 챙겨주어야 하므로 현재 위치에서 이동할 때 반드시 오른쪽이나 아래쪽으로 가야 한다.

따라서 고양이의 위치를 r 좌표를 기준으로 오름차순 정렬해 준다. (r 좌표가 동일하다면 c 좌표를 기준으로 정렬해 준다.) 

이후 r 좌표를 기준으로 고양이들의 위치를 정렬했으므로 c 좌표에 대해 LIS를 구해주면 된다. 

 

 

기본 LIS 문제만 풀어봤었는데 응용문제를 풀면서 감을 잡을 수 있어서 좋은 문제였다. ㅎㅎ

 

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/23035
public class Main_23035 {
    private static int N, M; // 가톨릭대 크기
    private static List<Position> positions; // 고양이의 위치


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

        int max = getMax();
        System.out.print(max);
    }//main


    private static int getMax() {
        int total = positions.size(); // 가톨릭대 안에 있는 고양이들 수
        int cnt = 0; // 밥을 챙겨줄 수 있는 고양이의 최대 마릿수
        int idx, curC;
        int[] dp = new int[total + 1]; // c 좌표 저장

        for(Position position : positions) {
            curC = position.c; // 현재 고양이 위치

            // 수업에 늦지 않고 갈 수 있는 위치에 고양이가 있다면
            if (curC >= dp[cnt]) {
                dp[++cnt] = curC;
                continue;
            }

            idx = getIndex(curC, cnt, dp);
            dp[idx] = curC;
        }

        return cnt;
    }//getMax


    private static int getIndex(int cur, int end, int[] dp) {
        int start = 0;
        int mid;

        while(start < end) {
            mid = (start + end) / 2;

            if(dp[mid] > cur) end = mid;
            else start = mid + 1;
        }

        return end;
    }//getIndex


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 가톨릭대 크기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 고양이의 수를 나타내는 정수가 주어진다.
        int K = Integer.parseInt(br.readLine());
        positions = new ArrayList<>(K); // 고양이의 위치

        // 고양이의 위치를 나타내는 정수 r, c가 주어진다.
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // 가톨릭대 밖에 고양이가 존재할 수 있다.
            if(r > N || c > M) continue;

            positions.add(new Position(r, c));
        }

        // 정렬
        Collections.sort(positions);
        br.close();
    }//init


    private static class Position implements Comparable<Position> {
        int r;
        int c;
        public Position(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public int compareTo(Position o) {
            if(this.r == o.r) return this.c - o.c;
            return this.r - o.r;
        }

        @Override
        public String toString() {
            return "r=" + r + ", c=" + c + '}';
        }
    }//Position


}//class