99클럽 코테 스터디 30일차 TIL

미들러

문제

1965번: 상자넣기

#동적계획법

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

풀이

상자가 일렬로 늘어서 있을 때 큰 상자에 작은 상자를 넣을 때 한 번에 넣을 수 있는 상자의 최대 개수를 구하는 문제이다.

동적계획법을 사용하여 문제를 해결한다.

배열 d에 해당 요소를 포함한 상자의 최대 개수를 저장한다.

i번째 요소를 포함한 상자의 최대 개수는 이전에 나온 상자의 개수 중 최댓값 + 1이다. (a[j] < a[i])

배열 d를 완성한 후 배열의 요소 중 최댓값을 출력한다.

코드

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

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());
		int[] a = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());

		int[] d = new int[n];
		d[0] = 1;
		int ans = 1;
		for (int i = 1; i < n; i++) {
			d[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i])
					d[i] = Math.max(d[i], d[j] + 1);
			}
			ans = Math.max(ans, d[i]);
		}

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