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

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

문제

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

풀이/후기

예전에 풀었던 문제지만, 코테 스터디 문제로 선택되어 다시 풀게 됐다.

문제를 보자마자 dp로 풀어야겠다는 생각이 들었고,

어떻게 구현할지도 대략 그려졌다.

 

예전에 dp 공부하면서 풀면서도 이걸 어떻게 하라는거지? 했었는데..

이젠 문제 보자마자 dp로 풀어야겠다, 어떻게 하면 될까? 고민하는 스스로가 아주 뿌듯했다!

 

비록 초반에 작성한 코드는 오답이었지만, 명확히 이해하고 푼 것 같아 만족스럽다.

코드

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

public class Main {
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] arr = new int[N];
        StringTokenizer str = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
        	arr[i] = Integer.parseInt(str.nextToken());
        }
        
        int[] dp = new int[N];
        
        dp[0] = arr[0];
        int max = Integer.MIN_VALUE;
        
        for (int i=0; i<N; i++) {
        	dp[i] = arr[i];
        	
        	// 이전 수열에서 현재 수보다 작은 수 탐색
        	for (int j=0; j<i; j++) {
        		if (arr[i] > arr[j]) {
        			// 기존에 있던 누적합과 새로운 누적합 중에 더 큰 합을 저장
        			dp[i] = Math.max(dp[i], dp[j] + arr[i] );
        		}
        	}
        	max = Math.max(max, dp[i]);
        	
        }
        
        System.out.println(max);
    }
    
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/4e69bdb0ec7f5c634addf407242831f15b7b22e1

참고