하다보면 늘겠지

개울을 건넜다는 것은 돌 다리를 모두 건너고 난 이후이다!! dy[n+1]이 답임! import java.util.*; class Main{ static int[] dy; public int solution(int n){ dy[1]=1; dy[2]=2; for(int i=3; i

답을 직관적으로 알 수 있게 소형화하여 보텀업 방식으로 올라간다. 1번 계단으로 갈 수 있는 방법의 수는 1 2번 계단으로 갈 수 있는 방법의 수는 2 3번 계단으로 갈 수 있는 방법의 수는 1번에서 2계단 점프 or 2번에서 1계단 점프 1+2 = 3 1번 계단으로 갈 수 있는 방법에서 2계단 점프+2번 계단으로 갈 수 있는 방법에서 1계단 점프의 합 import java.util.*; class Main{ static int[] dy; public int solution(int n){ dy[1]=1; dy[2]=2; for(int i=3; i

모든 간선이 서로 연결되어있는 트리를 뽑아내는데 간선의 가중치 값이 최소가 되도록 만들어 내는 것이 최소 스패닝 트리 문제라고 한다. 작은 비용부터 정렬해놓고 작은 비용부터 선택해 나가면 된다! 선택을 할 때 회로만 되지 않는다면 된다! Union & Find로 회로 체크를 할 것!(함수 내용은 외우는게 좋다) 1.Union & Find 메서드 활용 import java.util.*; class Edge implements Comparable{ public int v1; public int v2; public int cost; Edge(int v1, int v2, int cost) { this.v1 = v1; this.v2 = v2; this.cost = cost; } @Override public in..

기존 배열 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 해당 인덱스의 값이 부모이다. 첫번째 Union(1, 2) fa = Find(1) = 1, fb = Find(2) = 2 -- 1 != 2 이므로 unf[1] = 2 [0, 2, 2, 3, 4, 5, 6, 7, 8, 9] 두번째 Union(2, 3) fa = Find(2) = 2, fb = Find(3) = 3 -- 2 != 3 이므로 unf[2] = 3 [0, 2, 3, 3, 4, 5, 6, 7, 8, 9] 세번째 Union(3, 4) fa = Find(3) = 3, fb = Find(4) = 4 -- 3 != 4 이므로 unf[3] = 4 [0, 2, 3, 4, 4, 5, 6, 7, 8, 9] 네번째 Union(1, 5) return ..

가중치 방향 그래프이므로 graph[a][b] = c or ArrayList 를 사용한다. 거리 비용을 기록해주는 dis 배열을 사용한다. PriorityQueue를 사용하여 출발 노드를 큐에 넣어주고(1,0) 시작한다. 출발 노드의 거리 비용을 dis[v] = 0 으로 초기화한다. 처음 정점인 1번 노드를 꺼내고 연결되어 있는 노드들을 탐색한다.(2, 3번 노드) now = 1; nowCost = 0; 1.인접한 2번 노드의 현재 거리 비용(M)이 현재 정점까지의 비용 + 2번으로 가는 비용(12) 보다 크면 2번 노드의 거리 비용으로 바꿔준다. dis[2] > 0 + 12 참 이므로 dis[2] = 0 + 12 = 12 그리고 해당 정점과 비용을 큐에 넣는다. (2,12) - 1번 정점을 통해서 2번..

3일 안에 와서 강연을 해도 되는거면 2일 전이든 1일 전이든 가서 하면 된다. 먼저 time을 기준으로 내림차순 정렬한다. 강연료가 큰 값을 기준으로 큐에서 빼야하니 우선순위 큐를 내림차순으로 사용한다. 3일 안에 오면 가능한 강연들을 큐에 넣고 최대 강연료가 되는 기업의 강연료를 구한다. 구한 강연료를 총 수입 answer 변수에 더하고 큐에서 뺀다. 2, 1일 안에 오면 가능한 강연들을 큐에 넣고 위의 과정을 반복한다. (여기서 3일 안에 기업의 강연료가 높으면 선택이 될 수도 있다.) 이중 for문에서 안 쪽 for문에 대해 바깥에서 초깃값을 정의하면 그 값이 유지가 된다. j = 2일 때 break; 됐다면 다음 for문이 돌 때 0, 1 이 아닌 2부터 시작한다. 안 쪽에서 초깃값을 정의하고 ..

일단 오는 시간 순서대로 정렬을 한다. 앞의 문제와는 다르게 참석해있는 친구를 계속 유지시켜주어야한다. 따라서 각 시간마다 상태 값(state)을 두어서 처리를 한다. 오는 시간과 떠나는 시간이 겹치게 되면 떠나는 것 먼저 처리를 해준다. 상태 값이 's' 이면 오는 것 'e' 이면 떠나는 것으로 구분하여 각 스텝마다 최대 인원을 계산한다. import java.util.*; class Time implements Comparable { public int time; public char state; Time(int time, char state) { this.time = time; this.state = state; } @Override public int compareTo(Time ob) { //시간..

회의 종료 시간이 제일 빠른 순서대로 정렬한다. 회의 종료 시간이 같을 때는 시작 시간이 빠른 순서대로 정렬한다.(예시 입력2) 시작 시간을 s 종료 시간을 e로 둘거다. 다음 회의의 시작 시간이 이전 회의의 종료 시간과 같거나 클때 회의 수를 증가시켜준다. 그리고 다음 회의의 종료 시간을 다시 마지막 회의의 종료 시간 변수(et)에 넣어준다. import java.util.*; class Time implements Comparable { public int s, e; Time(int s, int e) { this.s = s; this.e = e; } @Override public int compareTo(Time o) { //끝나는 시간이 같으면 시작 시간도 오름차순을 한다. if(this.e==o...

키 순서대로 오름차순 정렬을 하게 되면 몸무게만 비교해보면 된다. 키는 작으니 몸무게라도 커야한다. 선발되는 인원의 몸무게를 max값으로 두고 해당 몸무게보다 클 때만 선발해준다. cnt++ 그리고 선발된 인원의 몸무게를 다시 max값으로 둔다. import java.util.*; class Body implements Comparable { public int h, w; Body(int h, int w) { this.h = h; this.w = w; } @Override public int compareTo(Body o) { return o.h-this.h; } } class Main { public int solution(ArrayList arr, int n){ //선발되는 인원 수 int cnt =..

import java.util.*; class Point{ public int x, y; Point(int x, int y){ this.x=x; this.y=y; } } class Main { static int n, m, len, answer=Integer.MAX_VALUE; static int[] combi; static ArrayList hs, pz;//집의 좌표, 피자집 좌표 public void DFS(int L, int s){ //조합이 한개 완성됐을 때 //각 집의 피자배달 거리 구해서 더한 뒤 최솟값 구해야한다. //6개의 피자집 중 4개를 뽑는 15가지 경우가 들어간다. //combi에 들어감.(0,1,2,3 0,1,2,4 ...) if(L==m){ int sum=0; for(Point ..