소프티어 징검다리 java

문제링크

문제 접근

• 삼중 반복문 사용하면 시간초과
• 그렇다면 dp 활용
• 하나의 징검다리마다 해당 다리까지 건너온 최대 갯수 기록

코드

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

public class Main {

    public static void main(String[] args) throws Exception{
      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 answer = 0;
      int[] map = new int[N];
      int[] dp = new int[N];
      for(int i=0;i<N;i++){
        map[i] = Integer.parseInt(st.nextToken());
        dp[i] = 1;
      }
      for(int i=0;i<N;i++){
        for(int j=0;j<i;j++){ // 이전 j돌에서 i돌로 갈때 최대 갯수 기록
          if(map[i] > map[j]){
            dp[i] = Math.max(dp[i] , dp[j] + 1);
          }
        }
        answer = Math.max(answer, dp[i]); // 최댓값 기록
      }
      System.out.print(answer);
    }
}

결과

정리

• dp로 풀어야한다고 느낌은 오지만 풀이방법이 한번에 딱 떠오르지는 않는다.