[소프티어/Lv. 3] 징검다리 (JAVA)

🔺 문제

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

 

 

🧩  해결 아이디어

• DP (최장 증가 부분 수열)

for문을 돌리며 다음 돌 arr[i]이 현재 돌 arr[j]보다 높을 때, 둘 중 더 큰 값을 찾아 dp[i]에 값을 넣는다.

 

 

🔺 코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
 
      int N = Integer.parseInt(br.readLine());
      int[] arr = new int[N];
      int[] dp = new int[N];
 
      st = new StringTokenizer(br.readLine(), " ");
      for(int i = 0 ; i < N ; i++) {
        arr[i] = Integer.parseInt(st.nextToken());
        dp[i] = 1;
      }
 
      int ans = 0;
      
      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]);
      }
 
      System.out.println(ans);
    }
}
 

 

---

💬 느낀 점

최장증가부분수열 넘나 오랜만...

담에는 꼭 잘 풀어볼게요..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Softeer] 징검다리 - Java

 

[소프티어/자바] lv3. 징검다리