하다보면 늘겠지

dy[j]는 나에게 j분이 주어졌을 때 얻을 수 있는 최대 점수이다. d[16]은 16분이 주어졌을 때 얻을 수 있는 최대 점수 앞의 문제 처럼 앞에서 부터 탐색하면 해당 문제를 2번 풀 수 있게 되어버린다! 그렇기 때문에 뒤에서부터 탐색하여 1번씩만 풀 수 있게 한다. 갯수가 무한정이다 - 앞에서부터 갯수가 무한정이 아니다 - 뒤에서부터 i = 0일 때 j = 20 ~ 5까지 돔 - 제한 시간이 5분이라서 20 ~ 5분 문제 풀 수 있음 dy[20] = Math.max(dy[20], dy[20-5]+10) = 10 - 5분 걸리는 10점 문제 하나 풀음 ... dy[5] = Math.max(dy[5], dy[5-5]+10) = 10 - 5분 걸리는 10점 문제 하나 풀음 i = 1일 때 j = 20 ~..

동전의 종류가 많으면 DFS로 풀면 시간 초과가 난다. coin[i]는 동전의 종류가 들어있는 배열 [1, 2, 5] dy[i]는 i라는 금액을 만드는데 필요한 동전의 최소 갯수 coin[i]=1원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐 coin[i]=2원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐 coin[i]=5원 짜리로 거슬러주는 dy[i] 초기화 기존 값 보다 작으면 값이 바뀌어짐 dy[j - coin[i]] + 1의 의미는 기존 거슬러준 동전의 갯수에서 해당 동전의 종류를 하나 더 사용한다는 의미이다. dy[5 - coin[1]] + 1의 의미는 3원에서 거슬러준 동전의 갯수 에다가 2원을 하나 더 사용한다는 의미이다.(5원) dy[1..

여기도 마찬가지로 dy[i]를 사용 dy[i]는 i 번째 벽돌을 마지막으로 하는 최대 벽돌의 높이를 저장할 배열임 앞의 문제와 비슷하나 이전 벽돌 보다 좁아야하고 무게도 가벼워야한다. 따라서 현 지점이 더 커야 수열을 만드는 앞의 문제와는 달리 지금 문제는 현 지점의 무게가 더 작아야 쌓을 수 있다. 무게만 비교해주기 위해 벽돌의 넓이를 기준으로 내림차순 정렬 무게만 가볍다면 위의 벽돌로 쌓을 수 있다. import java.util.*; class Brick implements Comparable{ public int s, h, w; Brick(int s, int h, int w) { this.s = s; this.h = h; this.w = w; } @Override public int compare..

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열(Longest Increasing Subsequence)이라고 한다. dy[i]는 i 번째 숫자를 마지막 항으로 하는 최대 증가 수열의 길이를 저장할 배열임 dy[0]은 5를 마지막 항으로 하는 최장 길이 = 1 (5 하나 밖에 없으니) dy[1]은 3을 마지막 항으로 하는 최장 길이 = 1 (5보다 3이 작으니 3만) dy[2]은 7을 마지막 항으로 하는 최장 길이 = 2 (3과 5 둘 다 가능 3 7 or 5 7 둘의 길이가 같으니 아무거나) dy[3]은 8을 마지막 항으로 하는 최장 길이 = 3 (3과 5와 7 셋 다 가능 근데 7을 ..

개울을 건넜다는 것은 돌 다리를 모두 건너고 난 이후이다!! 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부터 시작한다. 안 쪽에서 초깃값을 정의하고 ..