희디비
[백준/S2/DP/자바] 11053 가장 긴 증가하는 부분 수열 본문
💡 문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
⌨ 입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
💻 출력 / 제한
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ( 시간 제한 1초 )
풀이 방법
DP 문제 입니다.
dp[i] = i번째 인덱스 까지 만들수 있는 가장 긴 증가 하는 부분 수열 입니다.
dp[i] = 1로 초기화 ( 가장 작은 부분 수열 길이가 1 )
코드와 예시로 보는 편이 이해가 빠를 듯 합니다.
ex) arr = new int {3, 1, 5, 2, 4}
i -> i 번째 인덱스를 마지막 으로 하는 ( 증가 하는 부분 ) 수열을 만들때,
j -> 부분 수열이 되는 수를 찾는다.
ex) 3번째 인덱스인 5를 마지막 으로 하는 부분 수열을 찾을 때 :
1, 2 번째 인덱스 중에서 부분 수열의 요소를 찾습니다.
dp[1] / dp[2]
dp[1] = 1;
dp[2]
arr[2] = 1
앞부분 (j = 1; j < 2;) 자신의 부분 수열이 없으 므로 dp[2] = 1
dp[3]
arr[3] = 5
앞부분 (j = 1; j < 3;) 3,1은 부분 수열이 된다.
dp[3] = Math.max(1, dp[1] + 1)
dp[3] = Math.max(2, dp[2] + 1)
dp[3] = 2
dp[4]
dp[4] (j = 1; j < 4;) 1은 2의 부분 수열이 된다.
dp[4] = Math.max(1, dp[2] + 1)
dp[4] = 2
dp[5]
dp[5] (j = 1; j < 5;) 3,1,2는 4의 부분 수열이 된다.
dp[5] = Math.max(1, dp[1] + 1)
dp[5] = Math.max(2, dp[2] + 1)
dp[5] = Math.max(2, dp[4] + 1)
dp[5] = 3
전체 코드
더보기
public class LongestSubsequence11053 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
int[] dp = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int index = 1;
while(st.hasMoreTokens()){
arr[index] = Integer.parseInt(st.nextToken());
dp[index] = 1;
index++;
}
int maxLength = 1;
for(int i = 1; i < arr.length; i++){
for(int j = 1; j < i; j++){
if(arr[i] > arr[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
maxLength = Math.max(maxLength, dp[i]);
}
}
}
System.out.println(maxLength);
}
}
'백준' 카테고리의 다른 글
[백준/G3/MST/자바] 14621 나만 안되는 연애 (0) | 2024.06.26 |
---|---|
[백준/G5/구현/자바] 11509 풍선 맞추기 (0) | 2024.06.23 |
[백준/S1/BFS/자바] 2178 미로 탐색 (0) | 2024.05.22 |
[백준/S3/DFS/자바] 2606 바이러스 (0) | 2024.05.07 |
[백준/S1/구현/자바] 2564 경비원 (0) | 2024.04.30 |