Cooper's devlog

가장 큰 증가 부분 수열:11055번 - JAVA 본문

Algorithm/Baekjoon

가장 큰 증가 부분 수열:11055번 - JAVA

cooper_dev 2020. 7. 21. 00:35

1.문제 링크

https://www.acmicpc.net/problem/11055

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수�

www.acmicpc.net

2. 문제 설명

3. 문제 접근

과정 요약

1.  arr[idx]값을 dp[idx]에 추가한다. (dp[idx] = arr[idx])

2.  dp 값이 다음 조건이 일치할 경우에 변경한다.

(1) arr[left] < arr[right]

(2) dp[right] < dp[left] + arr[right]

 

두 조건 만족 시, dp[right] = dp[left] + arr[right]

 

표를 이용한 에제 설명은 추후에...ㅎㅎ

4. 문제 풀이

 

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
36
37
38
39
40
41
42
43
44
package dp1_practice;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class most_biggiest_subsequence {
    static int [] arr;
    static int [] dp;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        
        int max = 0;
        arr = new int[n+1];
        dp = new int[n+1];
        
        for (int idx = 1; idx <= n; idx++) {
            arr[idx] = Integer.parseInt(st.nextToken());
        }
        
        for (int right = 1; right <= n; right++) {
            dp[right] = arr[right];
            for (int left = 1; left < right; left++) {
                if(arr[left] < arr[right] && dp[right] < dp[left] + arr[right])    
                    dp[right] = dp[left] + arr[right];
            }
        }
        
        for (int idx = 1; idx <= n; idx++)
            if(max < dp[idx])    max = dp[idx];
        
        System.out.println(max);
        
        br.close(); 
    }
}
 
  

 

<정답 확인>

 

'Algorithm > Baekjoon' 카테고리의 다른 글

사탕 게임:3085번 - JAVA  (0) 2020.07.21
일곱 난쟁이:2309번 - JAVA  (0) 2020.07.21
동물원: 1309번 - JAVA  (0) 2020.07.17
쉬운 계단 수 : 10844번 - JAVA  (0) 2020.07.17
정수 삼각형: 1932번 - JAVA  (0) 2020.07.16
'Algorithm/Baekjoon' Related Articles more
Comments