각 물건의 무게를 쪼갤 수 없고 넣냐 빼냐로 결정하는 0/1 배낭 문제이다. dfs나 백트래킹으로는 2**n 승으로 오래걸려 시간 초과가 난다. dp로 풀어야만 풀리는 문제 dp[i][j]: 물건 i 번째에서 배낭 무게가 j일 때의 물건 가치 dp를 나누는 경우의 수 1. i 번째 물건이 무게 j보다 클 때: i 번째 물건을 무게가 j인 경우에 넣을 수 없어 이전 물건에서의 무게가 j인 가치를 넣어준다. dp[i][j]=dp[i-1][j]; 2. i 번째 물건이 무게 j보다 같거나 작을 때: dp[i][j]=Math.max(dp[i][j-w[i]]+cost[i],dp[i-1][j]); 이 문제는 물건 무게가 0인 경우가 없는데 만약 있는 문제라면 dp[i][j]=0; 으로 초기화해준다. import ja..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 보자마자 dfs 풀이가 생각났으나 dp로 풀어보려고 했다. a,b,c 대신에 배열을 쓰면 좀 더 깔끔할 듯하다. 최종 dp[n]에 들어가는 수가 1로 시작해서 n을 만들 수 있는 경우의 수이니 n에서 1을 만드는 것과 방법의 수가 같다. 각각의 방법으로 현재 수 i를 만드는 방법 중 최소의 계산 횟수를 넣어준다. import java.util.Arrays; import java.util.Scanner; public class Main { static int answer; static int n; static int[] dp;..
시작지점으로 돌아가는 최소 거리를 찾아야 하므로 모든 경우를 살펴봐야되서 dfs + 백트래킹으로 풀면된다. 모든 지점을 모두 방문할 수 있는 경우는 많은데 그 중 시작지점인 1로 돌아올 수 있고 이미 구했던 답보다 새로 구한 전체 방문 거리가 더 작다면 갱신해준다. 중간에 구한 거리가 이미 구한 거리를 넘어가는 순간도 return처리를 해줘서 시간 초과를 막아줘야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int n; stat..
import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int v,e,k; static ArrayList[] list; static int vis[]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); v=sc.nextInt(); e=sc.nextInt(); k=sc.nextInt();//시작점 vis=new int[v+1]; list=new ArrayList[v+1]; for (int i = 1; i
function solution(tickets) { tickets.sort(); // 글자순 정렬 let vis=Array(tickets.length).fill(false); var answer = []; function dfs(cur,cnt,path){ if(cnt===tickets.length && answer.length===0){ //정렬했으므로 처음오는 경우의 수가 답 answer=path; return; } for(let i=0;i
1. 시작점을 기준으로 오름차순 정렬한다. 기준점은 시작점의 끝나는 지점이다. (end) 2. 만약 다음 배열의 시작점이 기준점(이전 지점)보다 먼저라면 범위가 겹치는 지점이다. 끝나는 점이 더 작은 걸로 end를 갱신한다. 3. 만약 다음 지점의 시작점과 기준점보다 크다면 범위가 겹치치 않는다. 현재의 end지점에 카메라를 설치하고 end를 새로운 범위의 끝점으로 갱신해라. 4. 반복 function solution(routes) { var answer = 1; routes.sort((a,b)=>a[0]-b[0]); let end=routes[0][1]; for(let i=1;i
www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import java.util.PriorityQueue; import java.util.Scanner; class edge implements Comparable{ int s; int e; int w; public edge(int s, int e, int w) { super(); this.s = s; this.e = e; this.w = w; } @Override ..
scanner로 입력받으면 시간 초과한다. union으로 합칠 때 트리 깊이가 더 작은 것을 더 큰 것에 붙여줘야한다. 안 그러면 시간 초과난다. (다른 애들을 검사할 때 깊이가 점점 더 깊어지기 때문에) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.StringTokenizer; // 정올 1863 종료 public class Main { static int n,m; static int[] parent; static int[] depth; public static ..
먼저 union-find 알고리즘으로 그룹을 연결해준다. vis배열 (해당 집합 그룹을 방문했는지)를 만든 다음 1번부터 n번까지 체크해준다. 이미 앞에서 방문한 집합에 속한 번호라면 pass 방문했던 집합에 속하지 않은 번호라면 1. 먼저 친구비를 내서 사귈 수 있는 친구인지 확인한다. 2. 해당 번호가 속한 집합의 vis를 true로 해주고 방문한 번호의 개수(cnt)를 1 증가시킨다. 3. 낸 비용만큼 answer를 증가시킨다. import java.util.Scanner; //친구비 public class B_16562_Main { static int n,m,k; static int[] money; public static void main(String[] args) { Scanner sc=new..
import java.util.Scanner; public class Solution { static int t,n,m; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc