https://www.acmicpc.net/problem/11053
이 문제를 풀기위한 방법은 여러가지가 있다.
이중 for문, 재귀로 풀 수도 있고 이진 탐색을 이용하여 풀 수도 있다.
이진 탐색 풀이는 다른 사람이 작성한 코드를 보고 이해는 했는데
솔직히 그 아이디어가 어떻게 사람 머리속에서 나오는지 이해가 안된다.
문제를 더 풀어보고 나중에 이 포스팅을 봤을 때,
다른 방법으로도 풀 수 있는 실력이 생겼는지 확인하려고 글을 남긴다.
내가 푼 방법은 이중 for문을 이용하여
앞쪽부터 Bottom Up 방식으로 채워나간 풀이이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
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()); // 입력으로 주어지는 수열의 길이를 읽어옴
String[] pool_temp = br.readLine().split(" "); // 수열을 문자열로 읽어와 공백을 기준으로 나눠서 저장
int[] arr = new int[n]; // 입력된 수열을 저장할 배열
Integer[] dp = new Integer[n]; // 가장 긴 증가하는 부분 수열의 길이를 저장할 배열
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(pool_temp[i]); // 문자열로 저장된 수열을 정수로 변환하여 배열에 저장
}
for (int i = 0; i < n; i++) {
dp[i] = 1; // 모든 원소는 적어도 자기 자신만으로 길이 1의 증가하는 부분 수열을 가짐
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // 현재 원소와 이전 원소를 비교하여 더 긴 증가하는 부분 수열을 구함
}
}
}
Arrays.sort(dp, Comparator.reverseOrder()); // 가장 긴 증가하는 부분 수열의 길이를 역순으로 정렬
System.out.println(dp[0]); // 결과 출력: 가장 긴 증가하는 부분 수열의 길이
}
}
'코딩테스트 > 백준 알고리즘 (BOJ)' 카테고리의 다른 글
[백준] 2529번: 부등호 (JAVA, 문제, 문제풀이) (2) | 2023.12.05 |
---|---|
[백준] 6588번: 골드바흐의 추측 (JAVA, 문제, 문제풀이) (0) | 2023.09.20 |
[백준] 1918번: 후위 표기식 (JAVA, 문제, 문제풀이) (0) | 2023.09.18 |
[백준] 2750번: 수 정렬하기 (C++, 문제, 문제풀이) (0) | 2021.08.10 |