문제
https://www.acmicpc.net/problem/11054
풀이
백준 11053. 가장 긴 증가하는 부분 수열의 문제와 매우 유사한 DP 문제입니다.
더보기
https://www.acmicpc.net/problem/11053
위 문제의 소스코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
int[] dp = new int[N];
Arrays.fill(dp, 1);
for (int i = 0; i < N; i++) {
arr[i] = sc.nextInt();
}
int max = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
//앞의 숫자와 비교하며 만약 작은 수가 있다면, 그 작은 수의 dp값에 1을 더하고 그 값을 현재 dp값과 비교해 큰 값을 넣는다.
if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(max, dp[i]);
}
System.out.print(max);
}
}
바이토닉 부분 수열 문제도 이를 활용한 것인데, dp를 두 번 선언하여 앞에서부터 뒤로 가며 최대 증가 수열 길이를 체크하는 dp1[], 그리고 뒤에서 앞으로 오면서 최대 증가 수열 길이 dp2[]을 저장합니다.
문제에서 주어진 입력 값 예시를 대입하면
dp1[] = { 1 2 2 1 3 3 4 5 2 1 },
dp2[] = { 1 5 2 1 4 3 3 3 2 1 }
로 나오게 됩니다.
그리고 dp1[]과 dp2[] 를 더해 가장 큰 값에 1를 뺀 값(겹치는 횟수 제외)이 정답입니다.
소스코드
import java.util.Arrays;
import java.util.Scanner;
public class B11054_가장긴바이토닉부분수열 {
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int N = sc.nextInt();
int[] nums = new int[N];
int[] dp1 = new int[N];
int[] dp2 = new int[N];
int[] dp = new int[N];
Arrays.fill(dp1,1);
Arrays.fill(dp2,1);
for(int i = 0 ;i<N;i++){
nums[i] = sc.nextInt();
}
for(int i = 0;i<N;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) dp1[i] = Math.max(dp1[i],dp1[j]+1);
}
}
for(int i = N-1;i>=0;i--){
for(int j=N-1;j>i;j--){
if(nums[i]>nums[j]) dp2[i] = Math.max(dp2[i],dp2[j]+1);
}
}
int ans = -1;
for(int i = 0;i<N;i++){
dp[i] = dp1[i]+dp2[i];
ans = Math.max(dp[i],ans);
}
System.out.println(ans-1);
}
}
'Java > BOJ' 카테고리의 다른 글
[BOJ] 백준 25195. Yes or yes (0) | 2024.02.26 |
---|---|
[BOJ] 백준 2573. 빙산 (0) | 2024.02.22 |
[BOJ] 백준 10610. 30 (0) | 2024.02.20 |
[BOJ] 백준 3005. 탈출 (0) | 2024.02.18 |
[BOJ] 백준 1238. 파티 (0) | 2024.01.20 |