[백준] 1965 상자넣기 - 동적계획법(Dynamic Programming, DP) + LIS(최장증가 부분 수열) JAVA

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

1965번: 상자넣기

코드설명

DP 문제입니다.

 

문제를 읽다보면 상자넣기가 곧 가장 긴 증가하는 부분수열 문제라는 것을 알 수 있습니다.

문제로직입니다.

1. DP : 각 위치에서 최대로 넣을 수 있는 상자개수를 의마합니다.

2. DP를 계산하는데, 각 원소 arr[i]에 대해 더 작은 값을 가지고있다면 DP[i] = Math.max(DP[i], DP[j] + 1]) 로 최대값을 넣어줍니다.

 

문제에서 주어진 입력입니다.

입력
5
1 5 2 3 7

DP값
1 2 2 3 4

 

코드

Math.max를 활용한 코드

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

public class Main {
	public static int T, N;
	public static int[] arr = new int[1001];
	public static int[] dp = new int[1001];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		dp[i] = 1;
    		int standard =arr[i];
    		for(int j=0; j<i;j++) {
    			if(arr[j] < standard) {
    				dp[i] = Math.max(dp[i], dp[j] + 1);
    			}
    		}
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(answer,  dp[i]);
    	}
    	System.out.println(answer);
    	
    	
    }
}

 

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

public class Main {
	public static int T, N;
	public static int[] arr = new int[1001];
	public static int[] dp = new int[1001];
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		dp[i] = 1;
    		int standard = arr[i];
    		for(int j=0; j<i;j++) {
    			if(standard > arr[j]) {
    				if(dp[i] < dp[j] + 1) {
    					dp[i] = dp[j] + 1;
    				}
    			}
    		}
    		
    	}
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(answer,  dp[i]);
    	}
    	System.out.println(answer);
    	
    	
    }
}

 

메모이제이션과 동적계획법을 활용한 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static int[] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		cache = new int[N+1];
		Arrays.fill(cache, -1);
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(LIS(-1) - 1);
	}
	
	public static int LIS(int idx) {
		
		if(cache[idx + 1] != -1) return cache[idx+1];
		int ret = 1;
		for(int next=idx+1; next<N; next++) {
			if(idx == -1 || arr[idx] < arr[next]) {
				ret = Math.max(ret, LIS(next) + 1);
			}
		}
		
		return cache[idx + 1] = ret;
	}
	
}