import java.util.ArrayList;
import java.util.Collections;
/**
* 벽돌은 가장 넓은 것이 아래에 위치
* 그리고 가장 무거운 것일 수록 아래 위치
*/
public class 가장높은탑쌓기{
static class Brick implements Comparable<Brick>{
public final int width, heigth, weight;
public Brick(int width, int heigth, int weight) {
this.width = width;
this.heigth = heigth;
this.weight = weight;
}
public int compareTo(Brick o){
return o.width-this.width;
}
}
static int[] dy;
static ArrayList<ArrayList<Brick>> list;
public static void main(String[] args){
int[][] input =
{
{25, 3, 4 }
,{4 ,4 ,6 }
,{9 ,2 ,3 }
,{16, 2, 5 }
,{1 ,5 ,2 }
};
int n=input.length;
ArrayList<Brick> arr=new ArrayList<>();
dy=new int[n];
for(int i=0; i<n; i++){
int a= input[i][0] ;
int b= input[i][1] ;
int c= input[i][2] ;
arr.add(new Brick(a, b, c));
}
System.out.print(solution(arr));
}
static int solution(ArrayList<Brick> arr){
//너비 순으로 내림차순
Collections.sort(arr);
dy[0]=arr.get(0).heigth;
int answer= dy[0];
//높이 비교 1부터
for(int i=1; i<arr.size(); i++){
//높이 tmp
int max_h=0;
//이전 벽돌 비교
for(int j=i-1; j>=0; j--){
//무게는 j가 커야한다. 그리고 그 중에 제일 높은 값을 구한다.
if(arr.get(j).weight > arr.get(i).weight && dy[j]>max_h){
max_h=dy[j];
}
}
//제일 높은 값을 구했으니, 그 값에 나의 높이를 더 한다.
dy[i]=max_h+arr.get(i).heigth;
//지금까지 높이 중 가장 큰 높이를 구한다.
answer=Math.max(answer, dy[i]);
}
return answer;
}
}
import java.util.Arrays;
public class 최대부분증가수열연습 {
static int dy[];
public static void main(String[] args) {
//수열
int[] arr = {5, 3, 7, 8, 6, 2, 9, 4};
System.out.println(solution(arr));
}
static int solution(int[] arr) {
int answer = 0;
dy = new int[arr.length];
dy[0] = 1;
//수열 순회
for(int i=1;i<arr.length;i++) {
//수열 수 저장
int max = 0;
//현재 수열 이전 값 중 작은 값있는지 탐색
for(int j=i;j>=0;j--) {
//현재 수열보다 작은 값 있으면, 거기에 저장된 수열 횟수 저장
if(arr[i]>arr[j]) {
max = Math.max(max, dy[j]);
}
}
//구해진 수열 수에 +1
dy[i] = max+1;
//최종적으로 가장 횟수 많은 부분 수열을 구함
answer = Math.max(answer, dy[i]);
}
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(dy));
return answer;
}
}
class Solution {
static int [] chkArr = new int[3];//삼총사
static int [] intArr;
static int answer = 0;
public int solution(int[] number) {
intArr = number;
DFS(0,0);
return answer;
}
void DFS(int lv, int s) {
if(lv == 3) {
int sum = 0;
for(int x : chkArr) sum+=intArr[x];
if(sum == 0) answer++;
}else {
for(int i =s; i< intArr.length;i++ ) {
chkArr[lv] = i;
DFS(lv+1, i+1);
}
}
}
}
결과
테스트 1
입력값 〉 [-2, 3, 0, 2, -5]
기댓값 〉 2
실행 결과 〉 테스트를 통과하였습니다.
테스트 2
입력값 〉 [-3, -2, -1, 0, 1, 2, 3]
기댓값 〉 5
실행 결과 〉 테스트를 통과하였습니다.
테스트 3
입력값 〉 [-1, 1, -1, 1]
기댓값 〉 0
실행 결과 〉 테스트를 통과하였습니다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
ArrayList<Person> list = new ArrayList<Main.Person>();
int size = sc.nextInt();
for (int i = 0; i < size; i++) {
list.add( T.new Person( sc.nextInt(), sc.nextInt() ) );
}
Collections.sort(list,Comparator.reverseOrder());
System.out.println(T.solution(list));
sc.close();
}
private int solution(ArrayList<Person> list) {
int max = Integer.MIN_VALUE;
int cnt = 0;
for (Person person : list) {
if(max<person.weight) {
cnt++;
max = person.weight;
}
}
return cnt;
}
class Person implements Comparable<Person>{
int height;
int weight;
public Person(int height, int weight) {
super();
this.height = height;
this.weight = weight;
}
@Override
public int compareTo(Person o) {
return Integer.compare(this.height, o.height);
}
@Override
public String toString() {
return height+" "+weight;
}
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class 피자배달거리DFS {
static int[] combi; //경우의 수를 채울 배열
static List<Point> hs = new ArrayList<피자배달거리DFS.Point>();
static List<Point> pz = new ArrayList<피자배달거리DFS.Point>();
static int answer = Integer.MAX_VALUE;
static int len,n,m;
public static void main(String[] args) {
피자배달거리DFS T = new 피자배달거리DFS();
n = 4; //2차원 배열 크기
m = 4; // 피자 집 선택 수
int[][] board =
{{0, 1, 2, 0}
,{1, 0, 2, 1}
,{0, 2, 1, 2}
,{2, 0, 1, 2}};
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if(board[i][j]==2) { // 피자집은 2
pz.add(new Point(i, j));
}else if(board[i][j]==1) {// 가정집 1
hs.add(new Point(i, j));
}//이외는 빈 곳
}
}
len = pz.size();
combi = new int[m];//경우의 수 배열
T.DFS(0,0);
System.out.println(answer);
}
//재귀는 피자집 기준으로 쌓고 있다.
void DFS(int L, int s) {
if(L==m) { // 경우의 수 다 채움
System.out.println(Arrays.toString(combi));
int sum = 0;
for(Point h : hs) {
int dis = Integer.MAX_VALUE;
//다 찬 경우의 수 배열에는 피자집 위치 정보가 있다.
for(int i : combi) {
dis = Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y)) ;
}
sum += dis;
}
answer = Math.min(answer, sum);
} else {
for (int i = s; i < len; i++) {
combi[L] = i;
DFS(L+1, i+1);
}
}
}
static class Point{
int x;
int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
}
