vis배열을 3차원으로 해줘야되는지 모르고 풀었다가,, 결국 풀었다 ㅠㅠ 인간승리 흑흑 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Monkey{ int x; int y; int cnt; int k; public Monkey(int x, int y,int cnt,int k) { this.x = x; this.y = y; this.cnt=cnt; this.k = k; } } public class B_1600_말이되고픈원숭이_Main { static int k,w,h; static int[][] map; static int xpos[]= {0,0,1,-1, 1, 2,2,1,-1,-2,-2,-1};//..
아기상어끼리 안전거리를 구하는 줄 알았는데 다시 읽어보니 모든 칸에서 가장 가까운 안전거리를 구하는 것이었다. 아기상어가 있는 곳은 안전거리를 업데이트하지 않도록 해준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Shark{ int x; int y; public Shark(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,m; static int xpos[]= {0,0,1,-1,1,1,-1,-1}; static int ypos[]= {1,-1,..
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Fish { int x,y; public Fish(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,sx,sy; // 상어좌표 static int[][] map; static int[][] dis;// 물고기까지의 거리 static int xpos[]= {0,0,1,-1}; static int ypos[]= {1,-1,0,0}; static ArrayList ..
dp[i][j] < i 번째 집 j색깔 색깔이 0인 경우 이전 집 dp[i-1][1]과 dp[i-1][2] 중 더 비용이 적은 것에서 현재 0을 칠하는 비용을 더해주는 방식으로 갱신해준다. n번째 집까지 다 칠한 경우 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중에서 가장 비용이 적은 것을 출력해준다. import java.util.Scanner; public class Main { static int n; static int[][] rgb; static int[][] dp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); rgb=new int[n][3]; dp=new ..
각 물건의 무게를 쪼갤 수 없고 넣냐 빼냐로 결정하는 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