[백준] DP - 11055번, 가장 큰 증가하는 부분 수열

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문) 수열 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)

---

풀이

이 전에 풀었던 가장 긴 증가하는 부분 수열 문제(11053번)과 비슷한 형식으로 풀었다.

https://yy-eun.tistory.com/111

[백준] DP - 11053번, 가장 긴 증가하는 부분 수열 (다른 풀이 봄)

 

1. 테이블 정의

• 입력값 n만큼 arr배열에 입력받고, 중첩 for문을 활용해 이전값과 현재값을 비교하여 최댓값 구하기

2. 점화식 : D[i] = D[j]+arr[i]

3. 초기값 : D[i] = arr[i]

 

11053번 문제는 <수열의 길이>가 중요해 count 횟수를 dp에 누적했다면,

11055번 문제는 <수열의 합>이 중요해 입력 값을 dp에 누적했다.

 

(예시) 답이 나오는 일부분의 로직만 작성하였다.

arr	1	100	2	50	60
D	1	1 + 100	1 + 2	1 + 2 + 50	1 + 2 + 50 + 60

D[i] 요소는 기본적으로 <자신>을 값으로 가지며,
이전 값과 현재 자신 값을 비교해서 현재가 더 클 때 <이전 값도 함께> 저장한다.

 

코드

 

import java.util.*;
import java.io.*;

public class Main {
    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];
        int[] d = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //수열 입력
        for(int i=0; i<n; i++) {
            if(st.hasMoreTokens()) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
        }
        //dp배열, 현재값이 이전값보다 클때만 입력값 누적.
        for(int i=0; i<n; i++) {
            d[i] = arr[i];
            for(int j=0; j<i; j++) {
                if(arr[j]<arr[i] && d[i] <d[j]+arr[i]) {d[i] = d[j]+arr[i];}
            }
        }
        int max = 0;
        for(int i=0; i<n; i++) {
            max = d[i]>max? d[i] : max;
        }
        br.close();
        System.out.println(max);
    }
}

---

생각 정리하고 코드 작성하는 데에는 생각보다 적은 시간이 걸렸다(30m).

비슷한 유형을 바로 전에 풀었기 때문이었음.

 

그런데도 불구하고 여러번 틀리게 되었는데 그 이유는 다음과 같다.

1) arr[i] 인데 arr[j]로 작성(: 이전 값 더하기)

2) 테스트 케이스 질문 게시판에서 찾다가 잘못 이해하고 <= 연산자 사용

• 이건 솔직히 너무 억울하다. 증가 수열이라 동일 값은 해당 안되게 작성했다가 동일값도 인정하게 수정했기 때문. 하지만 잘못 보고, 잘못 테스트한 나 자신을 탓해야지.... 후...ㅜ.

문제 제출 전 꼼꼼히 다시 한번 검토하자는 깨달음을 얻었다.

 

 

참고

테스트케이스 서칭하다가 발견한 블로그. 많은 도움이 되었음. https://joey09.tistory.com/108