import java.io.*; import java.util.*; public class Main { private static int[][]city; private static int[]root; private static int[]rank; private static int[]travel; public static void main(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken(..
해당 문제는 이분 탐색을 활용한 문제이다. 1. 이분탐색을 통해 간격을 찾는다. 여기서 간격은 mid값으로 구할 수 있다. ( left 값은 1, right값은 첫번째 집과 마지막 집 사이의 거리로 정해놓는다.) 2. 간격을 좁혀야하면 ( 해당 간격에서는 공유기를 c개수만큼 못 놓는다면 ) 범위를 왼쪽으로 줄여준다 ( right를 조정) -> mid 값이 작아짐 3. 간격을 넓혀도 되면 (해당 간격에서 공유기를 c개수만큼 or 그 이상 놓을 수 있다면) 범위를 오른쪽으로 넓힌다 (left조정) -> mid 값이 넓어짐 결국 마지막 cnt>=c 일 때의 mid 값이 최대 간격이 된다. import java.util.*; public class Main { static int[] house; public s..
1. priorities 배열을 우선순위 큐에 넣는다. 2. priorities 배열의 값과 배열의 인덱스 (location)를 pair로 하여 큐에 넣는다. 3. 큐가 empty가 아닐 때까지 while문을 돌면서, 우선순위 큐와 큐에서 각각 poll을 해준다. -> 우선순위 큐에서 poll된 값 ! = 현재 poll된 큐 의 우선순위 라면, poll했던 큐를 다시 넣고 큐에서 계속 poll -> add를 반복한다. ( 해당 우선순위의 요소가 나올 때 까지) 4. queue 에서 최종적으로 poll된 값의 location과 우리가 찾을 요소의 location이 같다면 종료해준다. import java.util.*; class pair{ int loc; int prior; public pair(int l..
11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 뿌요뿌요의 규칙 상.하.좌.우 4개의 같은 색깔의 뿌요가 모이면 모두다 터진다. 뿌요는 중력에 따라서 빈공간이 생기면 무조건 아래로 이동해야한다. 여러색의 뿌요는 동시에 같은 연쇄에서 터질 수 있다. 세번째 조건은 백준의 유명한 BFS 문제인 토마토를 떠올릴 수 있다 .그러하다 나는 이 문제가 시뮬레이션이 들어간 토마토라고 생각했다. 물론 뿌요뿌요는, 상.하.좌.우 모두 무조건 터지는게 아니라 '같은 색'이어야만 터질 수 있으므로 BFS와 DFS를 모두 사용가능 하기도 하다. 그러면 일단 나의 로직은 이러하다. 모든 색깔의 뿌요를 큐에 넣는다. 이 ..