1. 문제
https://www.acmicpc.net/problem/1965
2. 풀이 과정
처음에는 간단하게 (해당 데이터에서 최대 길이) = (해당 데이터보다 작고 앞에 있는 것 중 가장 큰 값) + 1을 해서 이중for문으로 구현했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] dp = new int[N];
int result = 0;
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
arr[i] = Integer.parseInt(st.nextToken());
for(int j=0; j<i; j++){
if(arr[j] < arr[i]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
result = Math.max(result, dp[i]);
}
System.out.println(result+1);
}
}
시간 제한이 큰 편이라 통과는 됐지만 더 빠른 방법이 있었다. 가장 긴 부분 수열을 이진탐색을 이용하여 구현하는 것이다.
1. 수열의 마지막 수보다 크면 size를 늘려서 넣어준다.
2. 수열의 마지막 수보다 작으면, 해당 수열에서 자신보다 작은 값 뒤에 넣어주자.
1) 자신과 같은 값일 때는 해당 자리에 넣으면 됨
2) 자신보다 작은 값 뒤에, 자신보다 큰 값 앞에 넣어야 함
//input
8
1 6 2 5 7 3 5 6
//process
[0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 6, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 5, 0, 0, 0, 0, 0]
[0, 1, 2, 5, 7, 0, 0, 0, 0]
[0, 1, 2, 3, 7, 0, 0, 0, 0]
[0, 1, 2, 3, 5, 0, 0, 0, 0]
[0, 1, 2, 3, 5, 6, 0, 0, 0]
이를 코드로 구현하면 아래와 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] result = new int[N+1];
int size = 0;
st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
arr[i] = Integer.parseInt(st.nextToken());
if(result[size] < arr[i]){
result[++size] = arr[i];
}
else{
int pos = getPos(result, arr[i], size);
result[pos] = arr[i];
}
}
System.out.println(size);
}
public static int getPos(int[] result, int now, int r){
int l = 0;
while(l < r){
int mid = (l + r)/2;
if(result[mid] < now){
l = mid + 1;
}
else{
r = mid;
}
}
return l;
}
}
결과
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 16198번 : 에너지 모으기 (0) | 2023.03.03 |
---|---|
[Java] 백준 14891번 : 톱니바퀴 (0) | 2023.03.03 |
[Java] 백준 6087번 : 레이저 통신 (0) | 2023.02.27 |
[Java] 백준 1406번 : 에디터* (0) | 2023.02.25 |
[Java] 백준 13549번 : 숨바꼭질 3 (0) | 2023.02.21 |