[백준 *Java] - 가장 큰 증가 부분 수열 (11055)

 

가장 큰 증가 부분 수열 문제보기

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

 

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

입력
첫째 줄에 수열 A의 크기 N(1 <= N <= 1,000)이 주어진다
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 <= Ai <= 1,000)

출력
첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

 

전에 풀었던 '가장 긴 증가하는 부분 수열' 문제와 비슷함으로 접근을 쉽게 하였습니다.

2차원 배열을 사용을 할 생각입니다. 

new int[2][A크기] 로 선언을 하여, 

[0][A] = 부분 수열 인덱스 번호를 담을 생각입니다.

[1][A] = 부부 수열의 합을 담을 생각입니다.

	0	1	2	3	4	5	6	7
	1	100	2	50	60	3	5	6
0 (idx)	1	2	2	3	4	3	4	5
1 (sum)	1	101	3	53	113	6	11	17

아래는 설계를 하고, 실패한 코드입니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static long [][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());

        DP = new long[2][A+1];
        int [] arr = new int[A];
        Arrays.fill(DP[0], 1);
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < A; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 합 초기화
        DP[1][0] = arr[0];
        for (int i = 1; i < A; i++) {
            int sum = 0;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && DP[0][j]+1 > DP[0][i]) {
                    sum += arr[j];
                    DP[0][i] = DP[0][j] + 1;
                }
            }
            sum += arr[i];
            DP[1][i] = Math.max(DP[1][i-1], sum);
        }
        
        System.out.println(DP[1][A-1]);
    }
}

 

 

테스트 케이스로 확인을 할 때, 정확한 값이 나옵니다.

하지만, 틀렸네요..

애초에 앞에서 풀었던 '가장 긴 증가하는 부분 수열' 이랑 로직을 겹쳐서 생각하는게 실책이었던 거 같습니다.

따로 다시 로직을 설계해서 풀었다면 금방 접근해서 풀었을 거 같습니다...

그리고 위의 실패코드는 실상 1차원으로 풀수 있다는 걸 알게 됐습니다.

 

1차원으로 다시 설계를해서 문제를 푼 코드입니다

아래 코드는 성공한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {
    static int [] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());

        DP = new int[A+1];
        int [] arr = new int[A+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= A; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 합 초기화
        DP[1] = arr[1];

        for (int i = 2; i <= A; i++) {
            DP[i] = arr[i];
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j]) {
                    DP[i] = Math.max(DP[j] + arr[i], DP[i]); 
                }
            }
        }

        int max = 0;
        for (int n : DP) {
            if (n > max) max = n;
        }
        System.out.println(max);
    }
}