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

📌 문제

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

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

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

**제약조건
1 ≤ N ≤ 3×103 인 정수
1 ≤ Ai ≤ 108 인 정수

**입력형식
첫 번째 줄에 돌의 개수 N이 주어진다.
두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

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

입력예제1

5
3 2 1 4 5

출력예제1

3

📌 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
      //(1) 시간복잡도를 생각해보자
      //N이 3*10^3 -> n^2 알고리즘 사용할 수 있음
      //(2) 알고리즘을 생각해보자 -> dp를 사용해야할 것 같다

      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 i=0; i<N; i++) {
        arr[i] = 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);
    }
}

📌 설명

해당 문제는 dp를 사용해서 돌을 밟았을 때의 최대 개수를 업데이트 해주면 되는 문제입니다.

• dp[i] : i번째 돌을 밟았을 때의 최대 개수

dp 배열을 업데이트 해주기 위해서는, 현재 내가 밟고 있는 돌을 밟았을때와 이전의 돌들을 밟고 현재 돌을 밟았을 때를 비교해서 더 큰 값을 dp에 저장을 해주면 됩니다. 그렇게 되면 dp에는 해당 돌까지 도달했을 때, 밟은 최대 돌의 갯수가 저장되어있는데요. 그렇기 때문에 마지막에 한번더 가장 큰 돌의 값을 result로 따로 저장해주어야 합니다.

• 실패