import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; class Pos{ //좌표값을 가지는 클래스 int y; int x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Main { static int n,m; static int[][] map; static List list=new ArrayList(); static boolean vis[]; //벽을 세운 곳 static boolean check[][];//copy배열 방문 여부 체크..
www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 걱정했는데 swexpert의 플로이드 와샬보다 알고보니 쉬운 문제였다. 거리를 초기화해줄 때 1000(맥주를 마실 수 있는 최대 거리) 보다 크면 -1로 양방향(여기 양방향 처리 안했다 틀렸다)으로 넣어준다. 양방향으로 넣어주는 이유는 시작점과 끝점 둘 중 하나라도 연결이 안되면(중간점과의 간선길이가 1000보다 큰 경우) 시작점 - 중간점 - 끝점 을 연결할 수가 없기 때문이다. 만약 시작점과 끝점 둘다..
부분 수열1은 O(n*n)이 가능해서 dp (이중 포문)으로 많이 풀고 이 문제부터는 n이 커지므로 이분탐색*for문 O(nlogn)으로 풀 수 있는 이분탐색이 필요하다. import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static int n; static int[] num; static ArrayList arr=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); num=new int[n+1]; for (int i = 1; i
나는 연결이 안된 사람을 -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,0 좌표에서 시작해서 0인 부분(처음 공기인 부분)과 -1(치즈가 녹아 공기가 된 부분)을 공기로 체크해준다. (공기: -1) 공기와 만나는 치즈는 녹을 치즈(2)로 만들어준다. 2의 개수를 세고 치즈를 모두 녹여준다(-1로 만들어줌) 만약 1인 치즈가 있으면 반복한다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y; int x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class B_2636_치즈_Main { static ..
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 ..