[백준알고리즘] dp - 11055번 가장 큰 증가하는 부분 수열 문제

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

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

아까 풀었던 가장 긴 증가 수열 문제 코드를 조금 바꾸면 풀리겠다 싶었다.

엇 처음에는 틀렸습니다가 나왔다..

단 하나 있는 예제의 출력값과 같게 나오기는 하는데 뭐가 문제였을까?

아..찾았다 뭐가 문제였나면

dp[j] + dp[i]로 해둔게 문제였다. 

dp[i]에는 이미 이전에 갱신해둔 dp값이 들어가 있으므로 거기에 dp[j]를 더하면 의도와 다르게 된다

그게 아니라  j 원소까지의 수열 최대합에 i 원본값(nums 배열에 저장된 값)을 더해야 하는것!

If문 조건도 마찬가지

package week1;

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

public class MaxPartialSequence {  //백준 11055번 가장 큰 증가 부분수열 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    //수열의 크기 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());    //수열 입력받음
        int[] nums = new int[N];
        int[] dp = new int[N];  //N크기만큼의 Dp배열 생성, 여기에 각 수열값들 위치까지 올수있는 부분수열중 최대 합이 들어갈것임
        int max = 0;    //가장 큰 부분수열 합
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            dp[i] = nums[i];  //기본적으로 자기 자신 값이 들어간다(자기 자신 하나가 일단 원소니까 기본적으로 넣어줌)
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + nums[i] > dp[i]) { //여기도 nums[]로 안해놔서 틀렸었다
                    /*증가하는 수열이 되어야 하니까 일단 j 원소의 크기가 i보다 작은지부터 확인,
                    dp[j]의 값에 자기 자신의 dp값을 더하는게 원래 dp값보다 크다면 갱신 */
                    dp[i] = dp[j] + nums[i];    //dp[j] + dp[i] 로해서 값이 잘못나오고있었다
                }
            }
            if(max < dp[i]) max = dp[i];   
        }
        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
    }
}

 

그런 실수를 했었는데 문제 예제랑 똑같이 나왔던게 어이없다 ㅋㅋㅋ운이 좋았던듯

무튼 앞으로도 dp문제 감을 차근차근 익혀가야겠다..~!