www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net package algo0428; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class B_15785_기차가어둠을헤치고_Main { static int n,m; static int[][] train; public static void main(String[..
function solution(N, road, K) { var answer = 0; const dist={};//양방향 정보 저장 for(let i=0;iArray(N+1).fill(-1));//1에서 갈 수 있는 지점 const pq=[[1,0]]; while(pq.length>0){ pq.sort((a,b)=>a[1]-b[1]);//비용 적은 순 리턴 const [v,cost]=pq.shift(); if(vis[1][v]==-1){//아직 방문 안되었다. 나중에 같은 점 방문하는 경우 항상 비용이 크다 vis[1][v]=cost;//지점 업데이트 for(let k=0;kK)continue;//거리가 k보다 크면 안된다. if(vis[1][next]==-1){//아직 방문 안한 곳이라면 진행 pq.p..
0에서 n까지 가는 dp문제이다. 처음에는 재귀로 dp 돌렸는데 거리가 n을 초과하거나 비용이 더 작을 때만 진행시켜도 시간 초과났다. 거리가 2배인 곳으로 순간이동하는 데 비용이 없어 최대한 순간이동 시켜주는 게 좋으므로 2의 배수라는 것을 처리해주기 위해 %연산자를 써서 n에서 시작해서 0 까지 가준다. 2이 배수가 아닐 때에는 순간이동해서 온게 아니므로 -1로 짝수로 이동해준다. function solution(n) { var ans = 0; while(n>0){ if(n%2==0){ n/=2; }else{ n-=1; ans+=1; } } return ans; }
높이를 깎아서 다른 높이를 전달할 수 있다 => 같은 위치더라도 다른 높이로 들어온다. 방문정보를 어떻게 전달할 지 몰라서 방문 처리가 어려워 dfs로 했다 package algo0424; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; int cut; intnum; int len; public Pos(int y, int x,int cut,int num,int len) { super(); this.y = y; this.x = x; this.cut=cut; this.num=num; this.len=len; } } public class S_1949_등산로조성_Solution { ..
www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 활성 바이러스를 조합으로 구한 후 돌린다. 활성 바이러스는 비활성 바이러스가 있는 칸을 지나갈 수 있다. package algo0424; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super..
변을 기준으로 하는 bfs문제는 처음 풀었다. 방문 기준을 어떻게 해야할지 고민했는데 시작점과 끝점이 연결된 변을 방문 표시하기 위해서 (y,x,yy,xx)를 하나의 쌍으로 방문 배열에 넣고 같은 것이 있는지 찾았다. 만약 vis배열에 있다면 방문했던 곳이므로 answer를 증가시켜주지 않는다. function solution(dirs) { var answer = 0; let xpos=[0,0,1,-1];//DURL let ypos=[1,-1,0,0]; const dict={ 'D':0, 'U':1, 'R':2, 'L':3 }; let vis=[]; let y=5 let x=5; for(let i=0;i
1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음) 2. 0인 곳의 처리 (bfs) 0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다. 0의 개수만큼 cnt를 1증가시켜준다. 3. 1이상 숫자인 곳의 처리 마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Sc..
www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net import java.util.Scanner; public class Main { static int n,m; static String s; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt();//s의 길이 s=sc.next(); StringBuilder sb=new StringBuilder(); f..
www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 반례 3 3 => 0 1 2 3 2 => 1 2 5050 99 => 1부터 100까지 10 4 => 1 2 3 4 10 5 =>0 1 2 3 4 5 슬라이딩 윈도우처럼 앞에서부터 더해가며 n보다 커지면 가장 앞의 수를 빼주면 되는 문제이다. 더해준 수의 시작점과 끝점을 구해줘야 되는데 끝점은 현재 인덱스 i이고 시작점은 초기 0으로 둔 다음에 수가 커서 빼줄 때마다 1씩 더해준다. 길이가 l이상일 때 import java.util.Scanner; pu..
a라는 사람과 b사람이 벌꿀을 채취하는데 벌집이 중복되지 않도록 해야된다. a라는 사람은 모든 행, 열 기준으로 고르는데 b라는 사람은 a와 같은 행이라면 열이 중복되지 않도록 해야하고 다른 행이면 상관없이 뽑는다. 1. collect 함수 a는 모든 경우를 전사적으로 구해주므로 list에 집어넣는다. (추후 다른 행이면서 열이 중복된 경우를 계산할 때 쓴다) b는 a와 행이 겹치지 않는 부분에서 subset을 돌려준다. 일단 이 함수에서 a의 최대값과 b의 최대값의 합의 최대값으로 answer를 갱신해주면 행은 같은 경우는 끝난다. 2. calculate함수 다른 행의 중복된 열을 구해준다. a라는 사람은 collect함수에서 전사적으로 모든 subset 경우를 구해줬다. a사람이 구한 리스트지만 이제..