[소프티어] LV3 : 징검다리 (java)

🧪 LV3 징검다리

---

난이도 : 🌟 LV3
유형 : 이분 탐색

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

📝 문제

---

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

 

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

 

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

 

제약조건

 

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

 

입력

 

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

 

출력

 

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

 

🚧  1) 이분탐색으로 푸는 방법

🧐 핵심 로직

---

dp의 마지막 요소보다 넣고자 하는 배열의 요소가 더 작을때마다 이분 탐색을 통해 배열의 요소를 대입해준다.

else {
    idx = binarySearch(0, len, stones[i]);
    dp[idx] = stones[i];
}

 

위의 코드가 성립하는 이유는 배열의 첫 네 원소가 [5,6,1,2]일 때 길이가 2인 증가 부분수열은 [5,6]과 [1,2]이 있다. 그 다음 수가 무엇이 될지는 모르겠지만 작은 정보를 유지할 때는 LIS를 문제없이 구할 수 있다.

 

가령 원 수열의 바로 뒤의 수이자 마지막 수가 3일 때나 11111일 때 모두 [1,2]는 LIS를 만들어낼 수 있다. ([1,2,3],[1,2,11111]) 하지만 [5,6]은 3일 때 LIS를 이어가지 못한다.

 

즉, 배열의 요소가 dp값 보다 작거나 같다면 배열의 결과 자체는 원하는 결과가 나오지 않지만 배열의 개수는 구하고자 하는 개수와 같을 것이다.

 

◈ dp의 배열의 길이는 대체를 하더라도 커지지 않는다.

    ◈ len의 크기가 변하지 않은 상태에서 dp에 값을 넣어주는 것 이기 때문에 문제가 없다.

 

◈ 요소가 대체 되고난 후 dp의 마지막 요소보다 큰 값이 나와서 추가되더라도 이전 요소보다 뒤에 있는 요소라서 문제가 없다.

 

💻 최종 코드 (최대 93 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static int[] dp;
    public static void main(String[] args) throws Exception {

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

        int n = Integer.parseInt(br.readLine());
        int[] stones = new int[n];
        dp = new int[n + 1];
        int len = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            stones[i] = Integer.parseInt(st.nextToken());
        }

        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (stones[i] > dp[len]) {
                dp[++len] = stones[i];
            } else {
                idx = binarySearch(0, len, stones[i]);
                dp[idx] = stones[i];
            }
        }

        System.out.println(len);

        br.close();
    }

    private static int binarySearch(int left, int right, int target) {
        int mid = 0;
        
        while (left < right) {
            mid = (left + right) / 2;

            if (dp[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

 

🚧  2) DP로 푸는 방법

🧐 핵심 로직

---

DP를 이용한 LIS 찾기

수열의 한 원소에 대해, 그 원소에서 끝나는 최장 증가 수열을 생각해보자. 그 최장 증가 수열의 k를 제외한 모든 원소들은 반드시 k보다 작아야 할 것이다.

 

따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각의 원소에서 끝나는 최장 증가 수열의 길이를 알고 있다면, k에서 끝나는 최장 증가 수열의 길이도 구할 수 있을 것이다.

 

(1, 5, 4, 2, 3, 8)의 배열을 예시로 들면 8 이전의 (1, 5, 4, 2, 3)까지의 수열 중 각각의 원소에서 끝나는 최장 증가 수열의 길이는 다음과 같다. 이들 중 가장 긴 (1, 2, 3)에 현재 수 8을 더한 (1, 2, 3, 8)이 8에서 끝나는 최장 증가 수열이 된다. 이러한 LIS 구하는 방법을 활용하여 구할 수 있다.

• 1에서 끝나는 LIS 길이 : 1 (1)
• 5에서 끝나는 LIS 길이 : 2 (1, 5)
• 4에서 끝나는 LIS 길이 : 2 (1, 4)
• 2에서 끝나는 LIS 길이 : 2 (1, 2)
• 3에서 끝나는 LIS 길이 : 3 (1, 2, 3)

💻 최종 코드 (최대 129 ms)

---

import java.io.*;
import java.util.*;

public class Main {

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

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

        int n = Integer.parseInt(br.readLine());
        int[] stones = new int[n];
        int[] dp = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            stones[i] = Integer.parseInt(st.nextToken());
        }

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

        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        
        System.out.println(max + 1);

        br.close();
    }
}