처음에는 정렬을 해버렸는데.. 수열의 위치 자체가 의미 있는 값이기 때문에 현재 나열된 순서대로 해결해야 한다.
현재 인덱스(i)의 값까지 감소하는 부분 수열의 길이를 정답 배열(i)에 담아두고 비교한다.
문제를 더 작은 단위로 쪼개어, 작은 단계의 답을 활용하는 알고리즘
작은 단위의 결과를 저장할 배열 등을 미리 만들어 저장해둔다.
Top - Down(재귀호출), Bottom-Up(반복문) 두 가지 접근이 존재한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int[] arr = new int[n+1];
int[] cnt = new int[n+1];
StringTokenizer st = new StringTokenizer(reader.readLine());
for (int i=1; i<=n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int ans = 0;
for (int i=1; i<=n; i++) {
cnt[i] = 1;
for (int j=1; j<i; j++) {
if (arr[j] > arr[i]) {
cnt[i] = Math.max(cnt[i], cnt[j] + 1);
}
}
ans = Math.max(ans, cnt[i]);
}
System.out.println(ans);
}
}
사실 알고리즘 개념을 봐서는 딱히 와닿지는 않았다... ㅎㅎ;
몇가지 문제를 풀어보니 이런 상황이구나~ 싶긴 했다.
정답을 위한 배열을 만들어두고, 재귀 혹은 반복문을 활용해서 이전의 값들과 비교한다! 라는 문제풀이 도구를 하나 얻었다.
좋은 글 감사합니다. 자주 올게요 :)