[소프티어] 징검다리

https://softeer.ai/practice/6293

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

 

다음 문제는 처음에 이중 반복문으로 쉽게 풀 수 있다고 생각했지만 현재 밟고있는 돌을 기준으로 다음 돌을 건너뛸 수 있기에 복잡하다 생각하였다.

 

일단 문제의 제약조건을 보면 N이 최대 3 x 10^3 이기 때문에 시간복잡도 O(n^2) 이 가능하다는 것을 알았다.

알고리즘으로는 어떤 것을 사용해야 할지 고민하다가 현재 밟고있는 돌과 다음 돌을 밟았을 때의 카운트 크기를 비교하기 위해 dp를 사용하기로 했다.

 

전체 코드

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));
        
      int N = Integer.parseInt(br.readLine());
      int[] arr = new int[N];
      int[] dp = new int[N];
        
      Arrays.fill(dp, 1);
      
      StringTokenizer st = new StringTokenizer(br.readLine());
        
      for (int n = 0; n < N; n++) {
        arr[n] = Integer.parseInt(st.nextToken());
      }
      
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i]) { //다음 돌이 현재 돌보다 높을 때
            //현재 돌을 밟았을 때와, 이전 돌을 밝고 현재 돌을 밟았을 때의 최댓값 비교
            dp[i] = Math.max(dp[i], dp[j] + 1);
          }
        }
      }

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