99클럽 코테 스터디 30일차 TIL (미들러): [백준][Java] 1965 상자넣기 - 실버2

 

문제 보기

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

 

 

풀이

https://mountain-noroo.tistory.com/254

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

위 문제와 거의 동일한 문제이다.

이번엔 제일 "큰" 증가하는 부분 수열이 아니라 제일 "긴" 증가하는 부분 수열이라는 차이가 있는 정도이다.

 

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

그래서 현재 nums 값을 더하는 대신 1을 더한다.

 

 

전체 코드

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] = 1;
      for(int j = 0; j < i; j++) {
        if(nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      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/1965.%E2%80%85%EC%83%81%EC%9E%90%EB%84%A3%EA%B8%B0

CodingTest_AutoSave/백준/Silver/1965. 상자넣기 at main · MetroDefro/CodingTest_AutoSave