📄 문제https://www.acmicpc.net/problem/18111 📝 풀이땅을 고르게 만들기 위해서는 먼저 목표로 하는 땅의 높이를 정해야 한다.  이를 위해 땅의 최소 높이와 최대 높이를 구해야 한다. 그 후, 목표 높이를 "최소 높이 ~ 최대 높이" 사이 값으로 지정하여 최적의 높이를 찾아 시간을 계산하면 된다.  땅의 최대 높이는 256이므로, 최소 높이에서 최대 높이까지 모든 경우를 확인해도 된다. 또한, 최대 높이가 크지 않으므로 땅의 정보를 2차원 배열 대신 1차원 배열에 저장할 수 있다. (해당 높이의 땅이 몇 개인지 저장하는 1차원 배열) 목표 높이를 정했으면 깎아야 할 블록의 개수와 쌓아야 할 블록의 개수를 계산한다. 깎아야 하는 블록의 개수: 해당 높이의 땅 개수 * (현재..

📄 문제https://www.acmicpc.net/problem/5525 📝 풀이문자열 Pn은 I로 시작하고 OI가 총 n번 나오는 규칙이 있다. 이 규칙을 이용해서 Pn이 포함된 개수를 찾으면 된다.P₁ = IOI = I + OIP₂ = IOIOI = I + OI + OIP₃ = IOIOIOI = I + OI + OI + OI... 우선 문자열을 char로 변경하고 OI가 나온 개수를 기록하기 위한 배열을 만들어야 한다.  그 후, 두 개씩 확인하면서 첫 번째가 O, 두 번째가 I인지 확인한 뒤 지금 OI가 몇 번 나왔는지 기록하면 된다.check[i] = check[i - 1] + 1 문자열을 char 배열로 변경한 후, 2개씩 확인하면서 첫 번쨰는 O, 두 번쨰는 I인지 확인한 뒤, OI가 총 ..

문제https://www.acmicpc.net/problem/9370  풀이이 문제는 출발지에서 도착지까지의 최단경로를 구했을 때, 그 최단경로에 g와 h 교차로 사이에 있는 도로를 지나가는지 확인하면 되는 문제이다.  따라서 다익스트라 알고리즘을 사용해서 풀이할 수 있다.  문제를 풀 때 고려해야 할 점은 최단경로가 여러 개일 때, 어떻게 g와 h 교차로 사이에 있는 도로를 지나가도록 할 수 있느냐이다. 이 부분에서 막혀서 풀이를 참고했는데 방법은 아주 간단했다.  방법 1g와 h 교차로 사이에 있는 도로를 지나가기 위해서는 그 도로에 우선순위를 줘야 한다. 따라서 모든 도로 길이에 2를 곱해서 저장한 뒤, g와 h 교차로 사이에 있는 도로 길이에 1을 빼서 우선순위를 주면 된다.  즉, 아래 그림과 ..

문제https://www.acmicpc.net/problem/16236 풀이이 문제는 조건이 많이 주어지기 때문에 조건을 잘 정리해야 한다.아기 상어는 자신보다 작은 크기의 물고기만 잡아먹을 수 있다.아기 상어는 자신보다 작거나 같은 크기의 물고기가 있는 칸으로만 이동할 수 있다.잡아먹을 물고기가 없다면 엄마 상어에게 도움을 요청한다.잡아먹을 물고기가 1마리라면 그 물고기를, 2마리 이상이라면 가장 가까운 거리에 있는 물고기를 잡아먹는다.거리가 같다면 가장 위에 있는 물고기를, 같은 높이라면 가장 왼쪽에 있는 물고기를 잡아먹는다. 가장 중요한 조건은 물고기를 잡아먹는 조건이다. 그냥 BFS 탐색을 수행해서 물고기까지의 최단 거리를 구하면 된다고 생각할 수 있지만, 물고기를 잡아먹는 조건이 3가지나 주어지..

문제https://www.acmicpc.net/problem/1005 풀이건설 순서 규칙이 있는 방향 그래프(사이클X)이므로 위상 정렬을 사용해서 문제를 풀 수 있다.  위상정렬 문제를 푸는 것처럼 문제를 풀면 되지만, 목표한 건물을 짓는데 걸리는 시간을 구하기 위해서는 각 건물을 짓는데 소요되는 시간을 기록해야 한다. 문제에서 주어진 예시를 보면, 4번 건물을 짓기 위해서는 2번, 3번 건물이 지어져있어야 하므로 두 건물을 짓는 시간 중 최대 시간만큼 기다려야 한다. 따라서 4번 건물을 짓기 위해서는 10초 + Max(1초, 100초) + 10초 = 120초가 소요된다. 이러한 로직을 위상정렬을 수행할 때 추가해서 문제를 풀면 된다. 자세한 내용은 코드를 참고하면 된다. 코드import java.io...

문제https://www.acmicpc.net/problem/14889 풀이N명을 N / 2명씩 두 개의 팀으로 나눠야 한다. 즉, N명 중에서 N / 2명을 고르는 것(순서 상관X)이므로 조합을 사용하면 된다.  DFS 메서드(재귀)를 통해 N / 2명을 다 고른 후, 스타트 팀의 능력치와 링크 팀의 능력치를 구해야 한다. N / 2명을 고를 때 이미 방문 처리를 했으므로 방문 처리한 것은 스타트 팀, 하지 않은 것은 링크 팀으로 구분하면 된다.스타트 팀: used[i] = true링크 팀: used[i] = false 스타트 팀과 링크 팀의 능력치를 계산한 후, 두 팀의 능력치 차이를 최소값과 비교해 갱신하면 된다. 코드import java.io.BufferedReader;import java.io...

문제https://www.acmicpc.net/problem/1937 풀이n이 500이라 모든 위치에서 DFS를 돌려 최대 길이를 구하면 시간 초과가 발생한다. 따라서 DP(메모이제이션)를 함께 사용해야 한다. 대나무 숲 정보를 저장하기 위한 배열 외에도 dp 배열을 하나 더 선언해서 각 위치에서 이동할 수 있는 칸의 최대 개수를 기록해야 한다. (+ 방문 확인 기능) 시간을 줄이기 위해서는 이미 탐색했던 곳을 다시 확인하지 않아야 하므로, dp 배열에 값이 이미 기록되어 있다면 그 값을 바로 반환하면 된다. 그렇지 않다면 현재 위치에서 네 방향을 모두 탐색해야 한다. 이때, dfs 메서드를 호출해서 다음 칸에서 이동할 수 있는 칸의 최대 개수를 구해야 한다. 그리고 그 값을 현재 위치의 dp 배열에 더..

문제https://www.acmicpc.net/problem/1043 풀이진실을 아는 사람들과 같은 파티에 속하면 해당 파티에는 과장된 얘기를 할 수 없다. 즉, 진실을 아는 사람과 같은 파티에 속하는지를 확인하면 되는 문제이다. 따라서 유니온 파인드를 사용해서 그룹을 나눈 뒤, 같은 그룹에 포함되는지 확인하면 된다. 우선 진실을 아는 사람들을 같은 그룹으로 묶어야 한다.(union 메서드 호출) 편의상 첫 번째 사람을 대표자로 선정했다.  그 후, 파티의 정보를 입력받는다. 마찬가지로 같은 파티에 속하는 사람끼리 같은 그룹으로 묶는다. 이러한 과정을 반복하면 다음과 같이 된다.  이제 그룹을 다 나눴으므로 진실을 아는 사람과 같은 파티에 속하는지만 확인하면 된다. 각 파티의 대표자가 진실을 아는 그룹의..

문제https://www.acmicpc.net/problem/14500 풀이각 칸에서 DFS 탐색을 이용해서 4개 칸을 선택한 뒤, 선택한 배열의 합 중 최댓값을 찾으면 된다. 그냥 DFS 탐색을 이용해서 4개의 칸을 선택하면 ㅗ 모양을 처리할 수 없다는 문제가 발생한다. 그래서 총 2가지 방법을 사용해서 문제를 풀었다.  풀이 1첫 번째 방법은 DFS 탐색을 이용해서 3개의 칸을 선택한 뒤, 선택한 칸 주변의 칸 중 하나를 선택해서 최댓값을 고르는 것이다.  그러나 이 방법은 메모리를  너무 많이 잡아 먹어서 정석 풀이가 아닌 것 같다ㅎ.. 풀이 2두 번째 방법은 DFS 탐색을 이용해서 4개의 칸을 선택하고, DFS 탐색만으로 처리하지 못하는 ㅗ 방향을 따로 만들어서 확인해 주는 것이다. 이때, 회전과..

문제https://www.acmicpc.net/problem/2477 여담처음에는 이동하는 발자국만 생각해서 2차원 배열에 방문한 위치를 표시하고 BFS 탐색을 수행하는 방식으로 진행했다.("전체 크기 - 사각형에 포함되지 않는 영역"을 구하면 된다고 생각했었다. 대체 뭔 생각으로 했는지...?) 두 번째는 큰 사각형에서 포함되지 않는 사각형을 빼면 될 것 같다고 생각했다. 최대 가로/세로, 최소 가로/세로 길이를 구해서 계산을 했는데 이는 너무 단편적으로만 생각을 해서 틀렸다. (포함되지 않는 작은 사각형이 포함되는 작은 사각형보다 클 수 있음..!)  결국 다른 풀이를 참고했는데 이렇게 쉽게 풀 수 있는 것을 틀린게 너무 아쉽다..🤦🏻‍♀️ 풀이주어진 밭에서 자라는 참외의 수는 (육각형의 넓이 *..