[Baekjoon] 6221_The Bale Tower

문제(출처: https://www.acmicpc.net/problem/6221)

---

< The Bale Tower >

 

문제 풀이 

 

건초 더미를 오름차순으로 정렬 후 탐색하며 앞의 건초 더미가 현재 건초 더미보다 너비와 깊이가 모두 작은지 확인한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class _6221_ { // The Bale Tower
	static class Pair {
		int w, b;

		public Pair(int w, int b) {
			this.w = w;
			this.b = b;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		ArrayList<Pair> list = new ArrayList<>();
		int dp[] = new int[n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			list.add(new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			dp[i] = 1;
		}

		Collections.sort(list, new Comparator<Pair>() {

			@Override
			public int compare(Pair o1, Pair o2) {
				if (o1.w == o2.w) {
					return o1.b - o2.b;
				}
				return o1.w - o2.w;
			}
		});

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (list.get(j).w < list.get(i).w && list.get(j).b < list.get(i).b) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}

		int result = 0;
		for (int i = 0; i < n; i++) {
			result = Math.max(result, dp[i]);
		}

		System.out.println(result);
	}
}

변수)
n : 건초 더미의 개수
list : 건초 더미의 정보를 저장하는 ArrayList
dp : 규칙을 지켜 쌓을 수 있는 탑의 높이 
result : 규칙을 지켜 쌓을 수 있는 가장 높은 탑의 높이 

 

건초 더미의 개수를 입력받는다. 건초 더미의 개수만큼 건초 더미 정보를 입력받아 ArrayList에 저장하고, dp를 1로 초기화한다. 건초 더미를 오름차순으로 정렬한다. 건초 더미를 탐색하며 앞의 건초 더미가 현재 건초 더미보다 너비와 깊이가 모두 작은지 확인한다. 

 

최종 dp를 탐색하며 최댓값을 출력한다. 

---

---