풀이 간단한 다익스트라 알고리즘 : 최단거리가 가장 짧은 노드를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로 ( 모든 원소를 앞에서부터 하나씩) 탐색 : O(V^2)의 시간복잡도 개선된 다익스트라 알고리즘 : 최단 거리가 가장 짧은 노드를 선택하는 가정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체 package 최단경로; import java.util.*; class Node implements Comparable { private int index; private int distance; public Node(int index, int distance) { this.index = index; this.distance = distance; } public int getI..
풀이 N에 가장 가까운 제곱수를 뺀 dp값의 + 1이다! dp[i] = Math.min(dp[i], dp[i - j * j] + 1) import java.util.Scanner; public class 제곱수의합 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int[] dp = new int[100001]; dp[0] = 0; dp[1] = 1; for(int i = 2; i
풀이 import java.util.Scanner; public class 이친수 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); long[] d = new long[92]; d[0] = 0; d[1] = 1; d[2] = 1; for(int i = 3; i
풀이 for(int i = N; i > 0; i--) { int day = i + date[i]; if(day > N + 1) dp[i] = dp[i + 1]; else dp[i] = Math.max(dp[i + 1], pay[i] + dp[day]); } 가장 중요한 조건! 뒤에서부터 계산을 해준다. N일차부터 1일차까지 계산 N일차일 경우에 일할 수 있는 날짜 계산. date[N] 이 1이면 일할 수 있고 아니면 일할 수 없음. 일할 수 있는 경우, (이번 일해서 받는 pay + dp[day] : 이번 일이 끝나고 받을 수 있는 pay)와 이번일을 안했을 경우의 값을 비교해준다 . dp[i] = Math.max(dp[i + 1], pay[i] + dp[day]); 뒤에서부터 계산을 차근차근해서, ma..
