(https://www.acmicpc.net/problem/11722)

접근 방법 🧐

---

감소하는 수열이 없으면 나 자신 그 자체가 최대이므로 감소 수열을 담는 D배열을 1로 모두 초기화한다.

마지막을 기준값으로 두고, 그 기준값까지의 배열을 모두 검사해서,

1. 기준 값보다 더 높은 숫자가 있으면 count를, 즉 D[i]의 값을 ++ 해주는거다.
2. 현재 길이와 이전까지 연결된 최대길이들에 +1을 한 것을 비교해서 최대인 것을 선택한다.

   D[i] = Math.max(D[i], D[j]+1)

이해하는데 도움이 된 블로그

내가 쓴 코드 ✍️

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int result = 0;
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		int[] D = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
			D[i] = 1;  // 자기 자신. 없으면 1이기에 1로 초기화
		}
		
		for(int i=0;i<N;i++) { //기준값
			for(int j=0;j<i;j++) { //이전값들
				if(A[j] > A[i]) {
					D[i] = Math.max(D[i], D[j]+1);
				}
			}
			result = Math.max(result, D[i]);
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
	}
}

느낀점 📖

정말 나를 너무 괴롭혔던 문제였다. 사실 지금도 모르겠다. 문제는 이해가 가는데 아니 그냥 이해가 안가서 구글링을 했고, 다른 사람의 풀이를 분석해서 제출했다..
아니 이거 정답률 60퍼센트 이상 뭐냐구.. 너무 어렵다구...

와카라나이..

---

풀이를 보다보니 LIS 알고리즘 이란게 있다고 한다. 이걸 알고 외우면 쉽게 푼다던데 정말 배움에는 끝이 없구나~ 정말 알고리즘 코드가 이 문제 통과 코드와 똑같네..

LIS알고리즘해설