Hyunebee

일단 가중치들에서 음수가 없으로 다익스트라 알고리즘을 활용한다. import java.util.ArrayList; import java.util.PriorityQueue; public class Practice1 { static ArrayList graph; static final int INF = 1111111; static class Node{ int to; int weight; public Node(int to, int weight) { this.to = to; this.weight = weight; } } public static int solution(int[][] data, int v, int via1, int via2, int start, int n) { int case1 = 0; int c..

public class Practice3 { public static int solution(int[][] items, int n, int k) { int[][] dp = new int[n+1][k+1]; int result = 0; for(int i = 0; i < n; i++){ for(int j = 1; j j){// 무게 총량이 넘어간 경우 dp[i+1][j] = dp[i][j];// 그전 무게로 전부 채워줌 }else{ dp[i + 1][j] = Math.max(dp[i][j], dp[i][j-items[i][0]] + items[i][1]); } } } return dp[n][k]; } public static void main(String[] args) { // Test code int[][..

public class Practice2 { public static int solution(int[] arr) { int[] dp = new int[arr.length + 1]; int result = 0; for(int i = 1; i

class Node { int val; Node next; Node(int val) { this.val = val; this.next = null; } } public class Practice2 { public static Node solution(Node[] lists) { if (lists == null || lists.length == 0) { return null; } return divideList(lists, 0, (lists.length-1)); } private static Node divideList(Node[] lists, int left, int right) { if(left == right){ return lists[left]; } int mid = left + (right - l..

4가지 방법이 있지만 이중에서 분할 정복을 사용해서 문제를 풀것이다. 1. 왼쪽 경우에서 가장 큰값 2. 오른쪽 경우에서 가장 큰값 3. 겹치는 경우를 비교 public class sol { public static int solution(int[] nums) { if (nums == null || nums.length == 0) { return 0; } return divideArr(nums, 0, nums.length-1); } public static int divideArr(int[] arr, int left, int right){ if(left == right){// 배열의 길이가 1일 경우 전부 나눠진 경우 리턴 return arr[left]; } int mid = left + (right -..

그리디 import java.util.*; import java.util.stream.Stream; class Money{ int Money; int time; public Money(int money, int time) { this.Money = money; this.time = time; } public int getMoney() { return Money; } public int getTime() { return time; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 배열의 크기 ArrayList arrayList = ..

그리디 도착시간과 가는 시간을 char형식과 매핑 이것을 정렬해서 쉽게 풀 수 있음 import java.util.*; class Time implements Comparable{ int time; char when; public Time(int time, char when) { this.time = time; this.when = when; } @Override public int compareTo(Time o) { if(this.time == o.time){ return this.when - o.when; } return this.time - o.time; } } public class Main { public static void main(String[] args) { Scanner sc = new..

그리디 여기서 생각을 해야할 것은 종료와 동시에 시작할 수 있다는것 종료시간을 기준으로 정렬하지만 종료시간이 모두 같을 경우는 시작 시간 기준으로 정렬해 계산 lamda 식으로 처음에 했지만 종료시간이 같을 경우를 포함할 수 없어 Compareble로 구현 import java.util.*; class Time implements Comparable{ int start; int end; public Time(int start, int end) { this.start = start; this.end = end; } //중요 //종료시간 = currentTime){ currentTime = arr.get(i).end; cnt++; } } return cnt; } } import java.util.*; cla..