[백준] 11053 가장 긴 증가하는 부분수열

문제보기

복습 겸 다시 한번 풀어봤다. 10분이상 생각해서 풀이 안떠오르면 바로 남의 답 보고 체득해야한다.

오답으로 가는 루트를 계속해서 개척하는건 창의성 발휘해야 하는 분들에게나 필요한거고

PS 머신 되려면 걍 무적권 체득 또 체득해야함

마치 모법답안의 풀이가 내 머릿속에서 나온것처럼 체득되어야 실전에서도 그게 나온다. 기억에서 나오면 이미 틀린거고 마치 내 생각인 양 나와야 한다.

충분히 깨닫고도 나는 또 기만에 빠져서는…. 암튼 이건 그런 문제다.

메인 아이디어는 주석에 적겠음

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

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

    int[] arr = new int[n];
    int[] len = new int[n];

    for(int i = 0 ; i < n ; i++ ){
      arr[i] = Integer.parseInt(st.nextToken());
    	// len은 기본적으로 1로 초기화한다. 아무리 짧아도 자기 자신으로 이루어진 부분수열은 있으니깐.
      len[i] = 1;
    }
		
    int max = 1;
    
    // i는 len[i]를 결정할 녀석이다. len[0]는 죽었다 깨어나도 어차피 1이므로 비교할 가치 x
    for(int i = 1 ; i < n ; i++ ){
      // j 는 i 보다 앞에있는 녀석들을 처음부터 쭉 훑는것임
      for(int j = 0 ; j < i ; j++ ){
        // 만약 j에 있는 값이 i보다 작고, 
        // j까지 온 부분수열의 합이 i까지 온 부분수열의 합보다 크거나 같으면
        // i는 스리슬적 j가 만들어놓은 부분수열의 뒤에 합류하면 된다
        if(arr[j] < arr[i] && len[j] >= len[i]){
          // j가 여지껏 만들어놓은 부분수열에 슬쩍 숟가락만 얹으면 된다.
          // 만일 더 좋은 조건의 j가 들어온다면 현재 for문이 돌아가는동안 알아서 교체된다
          len[i] = len[j]+1;
          if( len[i] > max ){
            max = len[i];
          }
        }
      }
    }
    System.out.println(max);

  }
}