728x90
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
// 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception {
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] dp = new int[n];
arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
dp[0] = 1;
for(int i=1; i<n; ++i) {
dp[i] = 1;
for(int j=0; j<i; ++j) {
if(arr[j] < arr[i] && dp[i] <= dp[j]) dp[i] = dp[j] + 1;
}
}
int max = 0;
for(int num : dp) {
max = Math.max(max, num);
}
bw.write(String.valueOf(max));
br.close();
bw.flush();
bw.close();
}
}
|
cs |
https://developer-mac.tistory.com/71
[Java]백준 11053번 :: 가장 긴 증가하는 부분 수열
백준 온라인 저지 11053번 - 가장 긴 증가하는 부분 수열 Java 알고리즘 문제풀이 풀이 DP(다이나믹 프로그래밍) 문제입니다. 큰 문제를 작은 단위의 문제로 생각해서 푸는 알고리즘인데, 코딩테
developer-mac.tistory.com
반응형