99클럽 코테 스터디 28일차 TIL (미들러): [백준][Java] 11055 가장 큰 증가하는 부분 수열 - 실버2

 

문제 보기

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

 

 

풀이

이전에 풀었던 가장 긴 증가하는 부분 수열과 로직이 거의 동일해서 쉽게 풀었다.

 

int[] dp = new int[N];
int max = 0;
for (int i = 0; i < N; i++) {
  dp[i] = nums[i];
  for(int j = 0; j < i; j++) {
    if(nums[j] < nums[i]) {
      dp[i] = Math.max(dp[i], dp[j] + nums[i]);
    }
  }
  max = Math.max(max, dp[i]);
}

0부터 N-1까지 i번째 수가 마지막인 부분수열 중 제일 합이 큰 수열을 dp에 넣는다.

이는 0부터 i-1까지의 dp를 탐색해 이루어진다.

i보다 작은 수가 마지막인 수열 중 최댓값을 구하는 것이다.

물론 이 수열들도 이 로직을 거쳤기 때문에 항상 최댓값을 가지게 된다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  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];
    for (int i = 0; i < N; i++) {
      nums[i] = Integer.parseInt(st.nextToken());
    }

    int[] dp = new int[N];
    int max = 0;
    for (int i = 0; i < N; i++) {
      dp[i] = nums[i];
      for(int j = 0; j < i; j++) {
        if(nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j] + nums[i]);
        }
      }
      max = Math.max(max, dp[i]);
    }

    bw.write(max + "");
    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Silver/11055.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%ED%81%B0%E2%80%85%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4

CodingTest_AutoSave/백준/Silver/11055. 가장 큰 증가하는 부분 수열 at main · MetroDefro/CodingTest_AutoSa