1. java import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Solution { static int t,n; static int[][] map; static int[] xpos= {1,-1,0,0}; static int[] ypos= {0,0,1,-1}; static int[][] vis; public static void main(String[] args) { Scanner sc=new Scan..
사용자를 2명으로 제한해줘서 그나마 다행인 문제 충전소까지 거리가 닿냐에 따라서 사용할 수 있거나 없거나 하는데 사용하는 충전소를 중복 조합으로 만들어준다. 중복조합이라고 해서 재귀를 돌릴 필요는 없고 충전소 개수만큼 for문을 돌려주면 된다 다른 충전소이면 총 충전량을 더해주고 같은 충전소이면 충전소가 제공하는 양만큼 (충전한 곳이 하나라도 있을 경우 둘 다 거리가 안닿으면 0) 더해준다. import java.util.ArrayList; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } class Charge{ int y,x,c,p; public Charg..
나는 연결이 안된 사람을 -1로 써줬다. 플로이드 와샬 알고리즘을 볼 때 s(시작점) 중간노드 (k) e(끝 점) 의 거리를 업데이트 해줄 때 중간에 연결이 안된 사람이거나 (dist[s][k]==-1 || dist[k][e]==-1) 두 지점은 연결되어 있고 dist[s][e]가 연결이 안되어있는 상태인 경우 dist[s][e]==-1 dist[s][e]=dist[s][k]+dist[k][e]로 업데이트를 해줬다. import java.util.Scanner; public class Solution { static int t,n; static int[][] dist; public static void main(String[] args) { Scanner sc=new Scanner(System.in); ..
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..
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)..