[Softeer/소프티어] 징검다리(최장 증가 부분 수열 : LIS) - 자바[Java]

https://softeer.ai/practice/6293

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

 

 

풀이

최장 증가 부분 수열 문제다.

DP를 사용하여 풀 수 있으며 O(n^2) 의 시간복잡도를 가진다.

DP를 사용하기 위해 돌의 개수 n만큼의 크기를 가지는 int형 1차원 배열 dp를 선언한다.

dp[i] = i번째 돌이 마지막 돌일 때  철수가 밟을 수 있는 돌의 최대 개수

 

주의할 점

• dp[n-1]에 최댓값이 저장되지 않는다. 따라서 최댓값을 따로 저장하여 dp 배열의 값을 구할 때마다 최댓값을 업데이트해야 한다.

 

로직

1. 돌의 개수 n을 입력받는다.

2. 돌의 높이를 저장할 int[] stones 배열과, int[] dp 배열을 선언한다. 둘 다 크기는 n만큼 할당한다.

3. 돌의 높이를 입력받아 stones 배열에 저장한다.

4. getStones(stones, dp) 메서드를 호출하여 철수가 밟을 수 있는 돌의 최대 개수를 구한다.

public static int getStones(int[] stones, int[] dp) : 동적계획법을 사용해 dp 배열에 값을 채워나가고, dp 배열에 저장된 값들 중 최댓값을 리턴한다.

    public static int getStones(int[] stones, int[] dp) {
        dp[0] = 1;
        int answer = 1;

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

            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }

• 무조건 1개 이상의 돌을 밟을 수 있으므로 dp[0]은 1이다. 또한 답을 저장할 answer도 1로 초기화한다.
• i 는 1부터 for문을 시작한다.
  • 인덱스가 i인 돌보다 앞에 있는 돌(stones[j])들 중 dp 값(dp[j])이 가장 큰 값을 구하여, 그 값에 1을 더한 값을 dp[i]에 저장한다.
  • dp[i] 값을 구하면 answer와 dp[i]를 비교하여 최댓값을 answer에 저장한다.
• answer를 리턴한다.

 

코드

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


public class Main
{
    public static void main(String args[]) throws IOException
    {
        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());
        }

        System.out.println(getStones(stones, dp));
    }

    public static int getStones(int[] stones, int[] dp) {
        dp[0] = 1;
        int answer = 1;

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

            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}

 

참고

• [Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)
• [알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)