가장 긴 증가하는 부분 수열 11053
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 IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int input [] = new int [N];
int d [] = new int [N];
for(int i = 0; i<N; i++) {
input[i] = Integer.parseInt(st.nextToken());
d[i] = 1;
}
for(int i =0 ; i<N ; i++ ) {
for(int j=0; j<i; j++ ) {
if(input[j] < input[i] && d[i] <=d[j]) {
d[i]+= 1;
}
}
}
int max = 0;
for(int i=0; i<N; i++) {
max = Math.max(max, d[i]);
}
System.out.println(max);
}
}
잘 모르겠어서 다른 블로그를 많이 찾아 보았다.
dp, 즉 다이나믹 프로그래밍 방법으로 풀었다.
일단 문제에 예씨로
10 20 10 30 20 50 이 나와있다.
이 값을 input 배열에 넣는다.
이때 같은 크기의 배열 d[] 를 만든다. 그리고 맨 처음에는 모든 값을 1로 초기화 한다.
정답을 리턴할 때 이를 사용할 것이다.
자세히 설명해보자면,
일단 맨 처음 10이 나온다.
뒤의 다른 숫자들은 고려하지 말고
만약 수열에 10밖에 없다고 해보자. 그러면 문제에서 요구하는 제일 길면서 증가하는 부분 수열의 길이는 1이다.
그래서 d[0] = 1 로 초기화한다.
그 다음 20이 나온다.
20은 10보다 큰 값이다.
10 20 이렇게 2개의 값만 보자면, 제일 길면서 증가하는 부분 수열의 길이는 2가 된다.
따라서 d[1] = 2 가 된다.
그 다음 10이 나온다.
10 20 10 이 되는데
이 세번째에 위치한 10은
앞의 10과 따져보아도, 10 10 으로 증가하는 수열이 아니고,
20과 따져보아도 20 10 으로 증가하는 수열이 아니다.
따라서 맨 처음 10에서 d[0] 에 1을 채워 넣었던 것처럼
이 10도 1을 채워넣는다. 그래서 d[2] = 1이다.
앞의 숫자들보다 작거나 같기 때문에 다시 시작하는 것처럼 생각하는 것이다.
그 다음 30이 나온다.
10 20 10 에서,
맨 앞의 10보다 30은 크다. 따라서 d[3] 에 +1 을 한다.
그리고 20보다도 크다. 따라서 d[3] 에 +1을 한다.
이렇게 하면 10 20 30 으로 증가하는 수열이 완성된다.
그런데 세번째 위치한 10을 보자.
10 20 10 30 은 증가하는 수열이 아니다.
따라서 이 경우에는 d[3] 에 +1을 해줄 필요가 없다.
그래서 코드에 보면, 아래와 같이 완성했다.
for(int i =0 ; i<N ; i++ ) {
for(int j=0; j<i; j++ ) {
if(input[j] < input[i] && d[i] <=d[j]) {
d[i]+= 1;
}
}
}30 에 해당할 경우 i=3 인데,
이 경우 j= 0 1 2 까지 for 문을 돌려보면,
j = 0 일때 --------------------- 이 경우가 맨 앞에 있는 10의 경우이다.
if(input[0] < input[3] && d[3] < = d[0] 이면
d[3] 을 1증가시킨다.
input[0] = 10 이고, input[3] = 30 이라 해당되며,
d[3] =1 이고, (맨 처음 d[] 값은 모두 로 초기화 되어 있다.)
d[0] = 1이다.
따라서 if 문의 조건을 만족하므로
d[3] 을 1 증가시킨다.
j =1 일때도 --------------------------- 이 경우가 두번째 위치한 20의 경우이다.
마찬가지로 조건이 만족되서 d[3] 을 1증가시키고 그 값은 3이 된다.
j =2 일 때를 보자. ----------------------------- 이 경우가 세번째 10의 경우를 고려하는 것이다.
input[2] = 10, input[3] = 30 이다.
그런데 d[3] =3, d[2] =1 이다.
따라서 조건문이 만족되지 않아서, d[3] 을 증가시키지 않는다.
즉, 30이 앞의 숫자들 10 20 10 보다 크므로 d[3] 값을 증가시킬 수 있지만,
10의 경우는 2번 있어서 모두 증가시키면 안 되고 1번만 증가시켜야 한다.
이를 위해 d[i] <= d[j] 라는 조건을 같이 넣어둔 것이다.