문제https://www.acmicpc.net/problem/26215 풀이해당 문제는 정렬 및 그리디로 접근했습니다. 코드 순으로 보자면 1. 입력 값을 우선순위 큐에 넣어줍니다. 이때 집에 쌓인 눈을 기준으로 내림차순 정렬해줍니다.2. while 큐 사이즈가 2미만일 때까지 반복해줍니다. 2-1. 2개의 값에 각각 1씩 빼주고, 그 값이 1이상일 경우 큐에 다시 넣어줍니다.3. while 순회를 마치고 큐 사이즈가 1일 경우, 값을 빼내어 time에 더해줍니다.4. time 값을 출력합니다. (1440을 넘어간다면 -1을 출력해줍니다.) 코드14,280 KB / 132 msimport java.io.*;import java.util.*;public class Main { static int..
문제https://www.acmicpc.net/problem/14567 풀이특정 과목을 수강하기 위해선 미리 수강해야 할 과목들이 있으며이를 고려하여 몇 번째(학기)만에 이수할 수 있는지 구하는 위상정렬 문제입니다.코드 순으로 보자면1. 입력 값의 간선을 고려해, 그래프 형성 및 진입차수를 체크하고2. 진입차수가 0인 노드를 큐에 넣어줍니다.3. (몇 학기만에 이수하는지 구하기 위해) bfs depth별 탐색을 진행합니다. 3-1. 큐사이즈 만큼 돌면서, 큐에서 빼낸 값이 몇 번째로 나왔는지 체크해줍니다.(ans배열에 마킹) 3-2. 큐에서 빼낸 값에서 다음으로 갈 수 있는 값의 진입차수를 1 감소시킨 후, 그 값이 0이라면 큐에 넣어줍니다.4. 순서 값이 담겨있는 ans 배열을 순회하며 출력..
문제https://www.acmicpc.net/problem/2281 풀이문제에 맞게 최솟값을 찾아야 하며, 최적화를 위한 DP를 고려해야 하는 문제입니다. 이름을 적을 때는 2가지를 고려해 노트에 적습니다.1) 다음 줄로 넘겨서 적을 때2) 이어서 작성할 때(M을 넘지 않는 경우)1번과 2번 케이스 중 작은 값을 리턴하는 방식으로 재귀를 진행합니다.코드 순으로 보자면1. 메모이제이션을 위해 dp 배열을 -1로 초기화해줍니다.2. 재귀를 진행합니다(첫번째 인자: 인덱스, 두번째 인자: 현재 사용한 칸의 수) 2-1. 인덱스가 N에 도달했다면, 더이상 탐색할 필요가 없기 때문에 0을 리턴해줍니다. 2-2. 이미 메모가 되어 있다면 메모된 값을 리턴합니다. 2-3. 다음 줄로 넘겨서 적을 때..
문제https://www.acmicpc.net/problem/22116 풀이2차원배열 시작점(0,0)에서 종료점(N-1, N-1)까지 최소한의 낙차로 이동하는 문제입니다. 방문처리 및 우선순위 큐를 사용하여 낙차가 낮은 값이 먼저 나오도록 했습니다.그다음 우선순위 큐에서 값을 빼냈을 때, res와 현재의 낙차 중 큰 값을 res에 저장했습니다.목적지에 도달하면 순회를 종료하고 값을 출력했습니다. 코드174,404 KB / 1,312 msimport java.io.*;import java.util.*;public class Main { static int N; static int[][] arr; static boolean[][] v; static List[] list; stati..
문제https://www.acmicpc.net/problem/14676 풀이해당 문제는 선행 조건에 따라서 건물을 지을 수 있는지 체크하고이미 지어진 건물이 있어서 건물을 파괴할 수 있는지 체크하는 문제입니다. 선행조건에 따라 해결하는 문제이다보니 위상정렬을 이용합니다.또한 건물이 지어진 개수가 몇개인지 파악하기 위한 배열을 생성합니다. 간선을 이어주는 과정에서진입 차수에 해당하는 두번째 인자의 경우 in[b] ++ 해줍니다. 쿼리에 맞게type이 1이고 타겟이 cur이라면in[cur]은 반드시 0이어야지 건물 생성이 가능합니다.이러한 이유는 선행조건(해당 건물을 짓기 위해 미리 지어야 하는 건물)이 달성되어야지만 지을 수 있기 때문입니다.in[cur]가 0이라는 것은 선행조건을 모두 달성했다는 의미입니..
문제https://www.acmicpc.net/problem/17485 풀이시작 행(0)에서 종료 행(r-1)까지 가는데 최단 거리(가중치)를 구하는 문제입니다.이전과 같은 방향으로 두번 연속 움직일 수 없는 조건을 고려해주면 되는 문제입니다. 실패 케이스처음에는 2차원 int 배열로 현재까지 온 최소 가중치를 저장했습니다.bfs 탐색에서는 직전 방향과 현재 방향과 동일한 경우를 제외하고dp[nr][nc] > dp[r][c] + arr[nr][nc]인 케이스에 대해서 다음으로 이동하도록 구현했습니다. 하지만, 이렇게 구현하다보니최소값이 저장된 dp배열에는 방향이 고려되지 않는 값이 저장되어 원하는 결과가 나오지 않았습니다. 이러한 점을 고려하여3차원 int 배열을 활용하여 현재까지 최소 가중치를 저장하..
문제https://www.acmicpc.net/problem/1941 풀이5x5 배열에서 조건에 맞는 팀원을 구할 수 있는 경우의 수를 구하는 문제입니다.조건: 팀원이 모두 인접해있어야 하며, 그룹 내 Y가 3개 이하로 존재해야합니다. 그래프 탐색을 시작하면서 위의 조건에 맞는 경우를 찾는 방법보다25개 중에서 7개를 선택했을 때모두 인접해있거나 그룹 내 Y의 개수가 3개 이하일 경우, 카운트 업을 해주는 것이 구현하기 쉽고 더 효율적입니다. 1. 순서와 상관없이 7개를 선택하기 위해, 조합을 구합니다. 1-1. 선택 과정에서 해당 번호에 맞는 칸을 방문처리 해줍니다. ex) 24번의 경우 (4,4)에 방문처리를 해줍니다. (r = 24/5 연산을 통해 4, c = 24%5 연산을..
문제https://www.acmicpc.net/problem/16947 풀이무방향 그래프에서 사이클이 있는 문제입니다. 간선을 바탕으로 형성한 그래프에서 사이클을 찾고사이클에 속한 노드들을 기준으로 bfs 탐색하는 방식으로 문제를 해결합니다. 사이클에 속하지 않은 노드들은 -1로 초기화를 시킨 상태에서사이클에 속한 노드들은 0으로 갱신해줍니다. 다음으로 이동할 노드가 사이클에 속한 노드가 아니라면사이클에서 가장 가까운 노드는 1(사이클 노드의 0에 더하기 1)그 다음으로 가까운 노드는 2(1에 더하기 1)로 갱신해줍니다. 코드30,240 KB / 676 ms / 2057 Bimport java.io.*;import java.util.*;public class Main { static int N; ..
