[백준] 가장 긴 증가하는 부분 수열 (java) Dynamic_programming
2020-03-02
가장 긴 증가하는 부분 수열 (백준> Dynamic_programming)
문제설명
수열 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 복사
6
10 20 10 30 20 50
예제 출력 1 복사
4
풀이
package Dynamic_programming;
import java.util.*;
//50min
public class beak_가장긴증가하는부분수열 {
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];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();
int max_idx = 1;
dp[0] = 1;
for(int i=1; i<n; i++) {
dp[i] = 1; // 필수!
for(int j=0; j<i; j++) {
if(arr[i]>arr[j] && dp[i] <= dp[j])
dp[i] = dp[j]+1;
else if(arr[i] == arr[j])
dp[i] = dp[j];
max_idx = Math.max(max_idx, dp[i]);
}
}
System.out.println(max_idx);
}
}
후기 (50min)
dp로 풀긴 풀었는데… 내가 푼것도 틀린건 아닌거같은데 뭐가 문제일까 흠
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();
int max = arr[0]; int idx =0; int answer=0;
while(idx < n-1) {
if(max < arr[idx+1]){
max = arr[idx];
idx = idx+1;
answer++;
}
else
idx++;
}//while
참고링크