[백준 1965번][Java] 상자 넣기 - 동적 계획법에 대한 고찰

www.acmicpc.net/problem/1965

1965번: 상자넣기

 

이 문제를 계기로 다시 종만북을 펼쳐서 DP를 다시 공부했는데, 새로운 깨달음을 얻을 수 있었습니다.

지금까지 DP 문제를 풀 때, 어떤 유형는 메모이제이션을 이용해 풀어야 되고 어떤 문제는 점화식을 찾아서 바텀업으로 풀어야 된다는 식으로 문제를 분류했었는데 그럴 필요가 없었습니다.

 

이때까지 바텀업 방식의 풀이를 이용했지만 약간은 불편했습니다. 뭔가 직관적이지 않다라는 느낌을 지울 수 없었기 때문입니다.

그럼에도 바텀업 방식을 고수했던 이유는 '재귀로 풀 수 없는거 아냐?'라고 생각했기 때문인데, 그게 아니였습니다.

 

핵심은 부분 문제를 어떻게 정의하느냐 였습니다. 부분 문제가 최적 부분 구조를 만족해야 됩니다.(이 부분은 전에도 알고 있었지만 그렇게 실질적으로 구현에 도움이 되진 않았고, 로직을 검증하는 용도로 사용됐습니다.)

 

최적 부분 구조를 이루기 위해 가장 중요한 건, 부분 문제에 이전의 상태 속성을 없애야 된다는 점입니다. 다시 말해 이전의 상태값이 다른 부분 구조에 영향을 주면 안됩니다. 이렇게 되면 메모이제이션을 할 수 없습니다. 그래서 재귀 함수의 파라미터를 정의할 때 신중하게 생각해야 됩니다. 파라미터가 이전의 상태로부터 계산된 정보인지, 해결되어야 하는 문제들을 나타내는 정보인지 분류해야 합니다.

 

재귀를 이용해 DP 문제를 코드를 짤 때는 이런 패턴이 돼야합니다. 현재 재귀 함수에서 할 수 있는 작업을 하고 다음 함수에 나머지 작업할 부분을 넘긴다. 하지만 결과값을 다음 함수에 넘기지 않고, 다음 넘겨진 재귀 함수에서 리턴받아 계산하는 패턴이 돼야 합니다. 

 

하지만 어떤 문제에 한 해서는 이전의 상태를 알아야 하는 경우도 있습니다. 흠... 아직은 아리까리하네요.

더 다양한 문제들을 풀어 보면 뭔가 나은 답이 생각날 것도 같습니다.

 

 

  

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] box, cache;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		box = new int[n];
		cache = new int[n]; Arrays.fill(cache, -1);
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 0; i < n; i++) {
			box[i] = Integer.parseInt(st.nextToken());
		}

		int ret = 0;
		for (int i = 0; i < n; i++) {
			ret = Math.max(lis(i), ret);
		}
		System.out.println(ret);
	}

	private static int lis(int index) {
		if(cache[index] != -1) return cache[index];

		int ret = 1;
		for (int i = index+1; i < n; i++) {
			if(box[index] < box[i]) {
				ret = Math.max(lis(i)+1, ret);
			}
		}
		return cache[index] = ret;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}