[Softeer] 징검다리 - Java

https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_187431&psProblemId=390 

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=390&submissionSn=SW_PRBL_SBMS_187431

---

1. 문제

돌의 개수 N이 주어지고, 높이가 점점 높은 돌을 밟으면서 지나가고 싶을 때

돌의 높이가 서쪽부터 동쪽까지 주어졌을 때 밟을 수 있는 돌의 최대 개수를 출력한다.

 

2. 풀이

최장증가부분수열 문제이다. dp를 사용하면 효율적인 문제이다.

arr[]에 입력 값을 넣고 dp[]에 각각 1을 넣는다.

for문을 0부터 N까지 돌리고 그 안에 for문을 0부터 i까지(미포함) 돌려서

arr[i] > arr[j]일 때 dp가 최대가 될 수 있는 값을 찾고 해당 값을 dp[i]에 넣어준다.

즉, dp[i] = Math.max(dp[i], dp[j]+1);을 반복하는 것이다.

내부 for문이 끝났을 때의 확정된 dp[i] 값과 ans를 비교하여 가장 큰 dp[] 값이 최대 길이(밟을 수 있는 돌 최대 개수)가 된다.

 

3. 코드

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


public class Main
{
    static int N, ans;
    static int[] arr, dp;

    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        solution();
        System.out.println(ans);
    }

    static void solution() {
        for (int i=0; i<N; i++) {
            for (int j=0; j<i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
    }
}

 

4. 사담

최장증가부분수열 dp 풀이는 흔하지 않은 유형이라고 생각했고 재밌는 문제였다.