Java

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근 방식 최대 8*8 배열이라 백트래킹 + BFS로 무식하게 풀 수 있는 문제다. 벽을 3개 이하로 세우는 것이 아니고 무조건 3개를 다 세워야하기 때문에 벽을 3개 추가했을 때마다 BFS를 진행해주면 된다. BFS는 바이러스가 있는 위치를 모두 큐에 넣어준 후에 0인 부분만 탐색을 진행하면서 카운트를 해주고 n * m에서 카운트를 빼주면 바이러스가 퍼지지 않은 지역의 넓이를 알 수 있다. 풀이 public class Main { static int n, m, max ..

문제 접근 방식 짝수 명의 직원들을 절반씩 나누어 두 팀으로 구성할 때 두 팀의 능력치 차이가 가장 적은 경우를 구해야 한다. 각 팀을 모두 조합할 필요는 없고 한 팀만 구해도 되는데 한쪽팀만 구하면 반대팀은 자동으로 구성되기 때문이다. 백트래킹을 이용해 절반인 n/2까지 재귀를 호출하며 팀을 짜주고 n/2일 때 현재까지 기록으로 각 팀간의 점수차를 구해주면 된다. 즉, 절반의 팀을 구하는 메서드와 각 팀의 점수를 계산하고 차이를 구하는 메서드가 필요하다. 풀이 class Main { static int n, m; static int min = Integer.MAX_VALUE; static int[][] stats; static boolean[] isUsed; public static void main(..

문제 접근 방식 수가 최대 11개까지만 있어서 무식하게 풀어도 가능한 기본적인 백트래킹 문제다. 간단한 과정은 다음과 같다. 각 연산자의 사용횟수가 아직 남아있는지 확인 남아있다면 사용횟수를 1 감소시킨 후 재귀호출 자기 자신으로 돌아오면 감소시킨 사용횟수 복구 식을 모두 사용했으면 현재 값을 비교해 최대최소 기록 풀이 public class Main { static int n, plus, minus, multi, div; static int min = 1000000001, max = -1000000001; static int[] arr; static boolean[] isUsed; public static void main(String[] args) throws IOException { Buffered..

문제 접근 방식 현재 큐에 남아 있는 우선순위 중 가장 큰 값이 등장하기 전까지는 빼서 다시 맨 뒤에 넣어주어야 한다. 그렇게 계속 진행하다 현재 값이 가장 큰 값이거나 같다면 빼주고 카운트를 1 증가시켜주면 된다. 다만 값을 뺄 때 목표로 하던 값인지를 확인해야 하는데 이를 객체를 하나 생성하여 우선순위와 목표인지 여부를 기록해 큐에 넣고 돌아주면 편리하다. 현재 가장 큰 값을 체크하기 위해 우선순위 큐를 사용하였지만 배열에 받아두고 정렬을 하여 값을 꺼낼 때마다 바라보고 있는 인덱스를 1씩 감소시켜도 문제없다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..

문제 접근 방식 기본적인 BFS 탐색을 사용한 최단거리 문제로 2차원 배열이 아닌 3차원 배열이라는 부분만 다르기 때문에 기존에는 동서남북으로만 탐색 했다면 위층과 아래층으로 올라가거나 내려가는 탐색도 포함시켜 주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int l, r, c; String[] input; char[] chars; boolean[][][] isVisited; char[][]..

문제 접근 방식 생긴 거만 봐도 DFS 문제인 것을 알 수 있지만 DFS만으로 풀고 제출하면 시간초과가 발생한다. DFS에 DP까지 활용해야 하는데 아래의 경우를 생각해 보자 이 사진에서 오른쪽 경우는 왼쪽이 이미 방문한 20부터의 순서를 그대로 반복하는데 이미 갔던 길을 다시 가는 거라면 굳이 또 갈 필요가 없이 해당 구간으로 가는 길에 계산된 값을 그대로 사용하면 된다. 즉, 처음 가는 구간이라면 계속해서 도착 지점에 방문할 때까지 탐색하고 탐색 중에 이미 방문한 곳이라면 그 구간에 저장되어 있는 값을 더 해준다. 방문 여부를 기록할 불리언 배열은 필요 없고 2차원의 DP 테이블에 값이 채워져 있으면 기존에 방문한 것을 알 수 있기 때문에 이를 활용해서 탐색을 진행해 주면 된다. 이번 문제가 아니더라..

문제 접근 방식 1차원 배열의 구간합 원리를 2차원 배열에 적용하면 풀 수 있는 문제다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위와 같은 배열이 주어졌을 때 2,2 부터 3,4까지의 구간합을 구하려면 2,2 ~ 2,4의 구간합 + 3,2 ~ 3,4의 구간합을 더해주면 된다. 1 3 6 10 2 5 9 14 3 7 12 18 4 9 15 22 위처럼 각 행마다의 누적합을 구해둔 후에 이 누적합을 이용해 각 행의 특정 부분의 구간합을 구해주면 된다. 예를 들어 2,2 ~ 2,4까지의 구간합은 2,4까지의 누적합에서 2,1의 누적합을 뺀 것이고 3,2 ~ 3,4까지의 구간합은 3,4까지의 누적합에서 3,1의 누적합을 뺀 것이다. 결국 x축을 기준으로 시작 x축부터 끝나는 x축까지 반복하며 ..

문제 접근 방식 각 자리의 수마다 경우의 수를 이전 자리의 수들을 활용해가며 DP 테이블을 채워주면 되는 간단한거 같은 문제지만 예외 케이스가 머리를 아프게 한다. 우선 11111111과 같은 일반적인 경우를 살펴보겠다. 1 1 1 1 1 1 1 1 1 2 3 5 8 13 21 34 위의 표는 첫 자리부터 각 자리수마다 만들 수 있는 경우의 수로 3번째 자리의 수에 올 수 있는 경우의 수는 3번째 자리를 독립적으로 사용한 경우나 2번째 자리와 합쳐서 두 자리 수를 만든 경우를 합친 것으로 규칙을 찾아보면 피보나치의 점화식과 같은 dp[i] = dp[i-2] + dp[i-1] 인 것을 알 수 있다. 하지만 이건 모든 수들이 일반적일 때의 경우로 다음과 같이 조심해야 할 부분이 있다. 0으로 시작하는 경우 ..