문제 제목 : 가장 높은 탑 쌓기
난이도 : 상
문제 유형 : 동적 프로그래밍(DP), LIS
추천 풀이 시간 : 50분 (못하면 2배 100분)
TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@
점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]
https://www.acmicpc.net/problem/2655
2655번: 가장높은탑쌓기
첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차
www.acmicpc.net
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static class Brick {
public Integer index;
public Integer area;
public Integer height;
public Integer weight;
public Brick(Integer index, Integer area, Integer height, Integer weight) {
this.index = index;
this.area = area;
this.height = height;
this.weight = weight;
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
Integer n = sc.nextInt();
ArrayList<Brick> brickList = new ArrayList<Brick>();
brickList.add(new Brick(0, 0, 0, 0));
for (int i = 1; i < n + 1; i++) {
brickList.add(new Brick(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
Collections.sort(brickList, (s1, s2) -> s1.weight - s2.weight);
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
if (brickList.get(i).area > brickList.get(j).area) {
dp[i] = Math.max(dp[i], dp[j] + brickList.get(i).height);
}
}
}
Integer maxHeight = Arrays.stream(dp).max().getAsInt();
int index = n;
ArrayList<Integer> resultList = new ArrayList<>();
while (index != 0) {
if (maxHeight == dp[index]) {
resultList.add(brickList.get(index).index);
maxHeight -= brickList.get(index).height;
}
index -= 1;
}
System.out.println(resultList.size());
for (int i = resultList.size() - 1; i >= 0; i--) {
System.out.println(resultList.get(i));
}
}
}'Algorithm > BAEKJOON' 카테고리의 다른 글
| [알고리즘-BFS] 숨바꼭질 (0) | 2023.01.24 |
|---|---|
| [알고리즘-DFS,BFS] DFS와 BFS (0) | 2023.01.23 |
| [알고리즘-DP] 기타리스트 (0) | 2023.01.23 |
| [알고리즘-DP] LCS (0) | 2023.01.21 |
| [알고리즘-DP] 가장 긴 증가하는 부분 수열 (0) | 2023.01.21 |