import java.util.PriorityQueue; import java.util.Scanner; class Bridge implements Comparable { int a; int b; double dist; public Bridge(int a,int b, double dist) { super(); this.a=a; this.b=b; this.dist = dist; } @Override public int compareTo(Bridge o) { if(this.disto.dist)return 1; return 0; } } public class S_1251_하나로_Solution { static int t,n; static PriorityQueue bridge; static int[] xlist;..
각 물건의 무게를 쪼갤 수 없고 넣냐 빼냐로 결정하는 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..
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 ..
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
hashSet은 중복되는 값이 들어온다고 해서 없애주기 위해 사용했다. 링크드 리스트를 배열과 조합하여 시작하는 숫자들(부모 노드들)은 배열에 넣고 해당 숫자에서 뻗어나가는 자식들은 노드리스트에 넣었다. import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static int n; static int start,tc; static LinkedList[] list; static int answer,total_cnt; public stati..
답의 초기값을 1로 초기화하지 않고 음수 등으로 초기화하면 테스트 한 개를 통과 못한다. 처음에는 1덩이이므로 (모두 1이상임) 1로 초기화해준다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static int n; static int t; static int map[][]; static int result; static int ypos[]= {0,0,1,-1}; static int xpos[]= {1,-1,0,0}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.ne..
원래 시작점 위치 (2인 곳)을 따로 찾아서 시작점으로 넣어줘야 할 것 같은데 모든 예제의 시작점이 같길래 그냥 (1,1)로 넣어줬다. 만약 다른 테스트 케이스도 돌리는 거라면 시작점도 따로 변수에 담아줘야 할 것이다. D4지만 가장 간단한 bfs예제였다. 끝나는 경우는 3인 곳을 끝까지 만나지 못한 경우를 flag변수의 false로 하여 조건 출력해주면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Solution { static int t; static int[][] map; static int[] xpos= {0,0,1,-1}; static int[] ypos= {1,-1,0..
import java.util.ArrayList; import java.util.Scanner; public class Solution { static int t,n; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int tc=1; String temp=""; while(tc!=11) { n=sc.nextInt(); String s=sc.next(); while(true) { boolean changed=false; for (int i = 0; i < s.length()-1; i++) { if(s.charAt(i)==s.charAt(i+1)) { String str=s.charAt(i)+""+s.charAt(i+1)..
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Solution { static int t,n; static int[][] map; static List core; static boolean[][] vis; static int[] xpos= {1,-1,0,0}; static int[] ypos= {0,0,1,-1}; static int res; static int max_connect; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc res) ..
좀 되는 대로 푼 시뮬 문제라서 다른 방법도 공부해야겠다 import java.util.Scanner; public class Solution { static int t,n; static int[][] map; static int [] xpos= {1,-1,-1,1}; static int [] ypos= {1,1,-1,-1}; static int ans; static boolean vis[]; static boolean vis_dir[]; static int sy,sx; public static void main(String[] args) { Scanner sc=new Scanner(System.in); t=sc.nextInt(); for (int tc = 1; tc