아이디어 MST 를 구하는 문제이므로 대표적인 방법들 중 취향에 맞게 선택해서 풀면 된다. 나는 오늘 처음 보는 알고리즘이라 둘 중 Kruskal 알고리즘을 사용했고, UNION-FIND 를 이용해 사이클을 방지하도록 했다. 다만 UNION-FIND 과정에서 서로 다른 그룹을 그룹화 할 때 그룹화 하기 위해서는 각 그룹의 루트 노드를 연결해줘야 하는데 이 부분에 실수로 입력 노드를 연결하는 방식을 취해서 애를 먹었다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import ..

아이디어 처음에는 치즈가 존재하는 칸을 찾고 이 칸을 기준으로 인접한 4칸을 탐색한 후 빈 칸이 몇 개인가를 카운팅하는 로직을 생각했으나 치즈 내부 공간은 치즈가 녹는 데 영향을 미치지 않으므로 이 방법을 사용할 수 없었다. 그래서 치즈가 없는 외부에서 dfs 또는 bfs 를 수행하고 치즈로 막힌 경우 다른 경로를 찾게함으로써 치즈 외부 빈칸을 모두 탐색하는 방식을 사용했다. 이 때 내부 공간과 구분하기 위해 탐색된 칸의 값은 음수로 설정해주었다. 이렇게 외부 공간을 표시한 후 현재 치즈가 녹으면 큐에서 제거해주고 아니면 다시 큐에 추가하는 방식을 사용했고 치즈를 담은 큐에 아무것도 남지않을 때까지 반복해 시간을 구했다. 풀이코드 import java.io.BufferedReader; import jav..

아이디어 먼저 BFS 를 통해 현재 상어의 위치에서 가까운 위치부터 탐색을 진행하며 먹을 수 있는 물고기가 있는지 확인한다. 이 때 자신보다 큰 물고기가 있는 칸은 상어가 통과할 수 없으므로 이 점에 주의해서 BFS 를 수행한다. 먹을 수 있는 물고기가 없으면 false 를 반환하고 먹을 수 있는 물고기가 있다면 1. 해당 물고기의 위치로 상어를 이동시키고, 2. 소요된 시간을 더해주고 3. 먹은 물고기 수를 늘려준 후 4. 먹은 물고기 수가 상어의 크기와 같다면 상어의 크기를 키워준다. 5. true 를 반환한다. 위 내용이 false 를 반환할 때까지 반복하면 문제에서 요구하는 답을 얻을 수 있다. 풀이코드 import java.io.BufferedReader; import java.io.IOExce..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 아이디어 각 지역에 낙하했을 때 얻을 수 있는 아이템은 아이템이 있는 지역과 낙하한 지역 간 거리가 수색범위를 벗어나지 않는 경우이다. 따라서 1. 모든 지역 간의 최단 경로의 길이를 구하고 2. 임의의 낙하 지역에서 타 지역과의 거리가 수색 범위를 벗어나지 않는 경우에 한해 해당 낙하 지역에서 얻을 수 있는 아이템을 계산하고 3. 이 값들을 비교해 최대값을 얻어내면 된다. 입력의 크기가 작아 플로이드..

아이디어 문제는 되게 길어보이지만 결국 정리하자면 정해진 시간 동안 1. 확산 2. 공기청정 과정을 수행하고 마지막에 남은 먼지 양을 체크하는 문제이다. 공기청정 과정은 배열에 담긴 값을 한 칸씩 밀면 되는 단순한 단계이고 약간 머리를 써야 하는 부분은 '확산' 이다. '확산'은 현 시점에서 먼지가 있는 모든 위치에서 동시에 일어나야 하므로 배열 하나만 사용할 경우 현 시점에 확산된 먼지가 동일한 시점에 재확산 되는 현상이 발생한다 따라서 '확산' 시에는 임시 배열을 만들어 임시 배열로 확산을 수행해야 한다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java...

아이디어 Sk 를 기준으로 양쪽을 잘라보면 S1 Sk+1 > ... > Sn 이므로 각각 증가하는 부분 수열, 감소하는 부분 수열임을 알 수 있다. 따라서 가장 긴 바이토닉 부분 수열은 배열의 각 원소를 Sk 로 놓고 가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열을 구한 후 바이토닉 부분 수열을 계산하고, 각 바이토닉 부분 수열 중 가장 긴 놈의 길이를 출력하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { publi..

아이디어 A ^ N = (A ^ N/2) * (A ^ N/2) 이므로 재귀함수를 활용하되 시간복잡도가 커지지 않도록 N/2 크기씩 줄여가며 재귀함수를 호출하면 충분히 통과가 가능하다. 지수 연산을 하는 exp() 메서드와 행렬 곱셈 연산을 수행하는 multiply() 메서드를 만들어 문제를 해결하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int[][] I; public static void main(String[] args) thr..

아이디어 출력을 보고 유추할 수 있는 것은 N = 24 일 때의 별은 N = 12 일 때의 별을 3개 출력한 결과라는 것이다. 따라서 재귀함수를 활용하면 문제를 해결할 수 있을 것이라 생각했고 각 별이 출력되는 위치가 다르기 때문에 좌표와 별의 크기를 입력으로 받는 재귀함수를 만들면 된다고 생각했다. 해당 함수를 draw(int i, int j, int N) 이라고 가정하고 예제를 살펴보면 draw(0, 0, 24) -> draw(0, 12, 12) -> draw(12, 0, 12) -> draw(12, 24, 12) 와 같이 N = 24 짜리 별을 위해서 (0, 12) 에서 시작해 N = 12 인 별, (12, 0) 에서 시작해 N = 12인 별, (12, 24) 에서 시작해 N = 12 인 별을 출력..