Softeer Lv.3] 징검다리(Java)

 

징검다리

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

 

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

 

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

제약조건

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

입력형식

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

출력형식

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

입력예제1

5 3 2 1 4 5

출력예제1

3

 

 

 

코드

쉬울줄 알고 단순하게 생각하고 풀었는데, 틀렸단다.

구글링 해보니 dp문제란다;; dp가 뭔지 잘 몰랐었는데, 풀어보니 대충 감이 오더라..

 

 

반례는 아래와 같은 반례를 처리해줘야 맞는 문제었다.

입력

6

3 2 1 6 4 5 

 

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 = new StringTokenizer(br.readLine());

      int N = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(br.readLine()," ");
      int[] rock = new int[N];
      int[] dp = new int[N];
      
      for(int i = 0; i < N; i++){
       rock[i] = Integer.parseInt(st.nextToken());
        dp[i]= 1;
      }
  
      
      // 6
      // 3 2 1 6 4 5
      for(int i = 1; i < N; i++){
        for(int j =0; j < i;j++){
          if(rock[i]>rock[j]){
            dp[i] = Math.max(dp[i],dp[j]+1);
          }
        }
      }
   
      
      Arrays.sort(dp);
      
      System.out.print(dp[N-1]);
      
    }
}

 

 

 

긴글 읽어 주셔서 감사합니다.

더 궁금하신 사항은 댓글로 문의해주시면 빠르게 답변드리겠습니다.