문제 백준 2473번 풀이 가장 떠올리기 쉬운 풀이는 3개의 수의 조합을 찾아 모두 탐색하는 방법입니다. 3개의 조합을 뽑는 경우의 수가 $ _{n}C_{3} $이 될텐데 $ N $이 $ 5,000 $이니 TLE나기 좋은 시간복잡도입니다. 최적화를 해보겠습니다. 2개의 수(각각 $ A_{i}, A_{j} (i \neq j) $)를 뽑았을 때, 그리디하게 $ -(A_{i} + A_{j}) $와 가까운 수를 찾으면 0과 가까운 수를 만들 수 있습니다. 이 외의 나머지 수들은 답이 될 수 없습니다. 들어오는 수열을 정렬해놓고, $ -(A_{i} + A_{j}) $과 가까운 수를 이분 탐색을 사용하면 $ O(N^2logN) $에 풀 수 있습니다. 소스코드 #include using namespace std; i..

문제 백준 11985번 풀이 점화식: $ dp[i] = i번째\ 오렌지까지\ 담았을\ 때\ 드는\ 최소의\ 비용 $ 으로 두었을 때, $ i $번째 오렌지에 대해서 $ k ( 1 \le k \le n) $개만큼 한 상자에 담는 경우를 처리하면서 dp table을 채워줍시다. 자세한 설명은 코드에서 이어가겠습니다. 이해안되거나 질문 있으시면 댓글 남겨주세요. 정답은 $ dp[n] $에 들어간 값이 됩니다. 모든 $ i (1 \le i \le n) $에 대해서 $ n $번 방문하니 시간복잡도는 $ O(n^2) $이 됩니다. 소스코드 #include using namespace std; typedef unsigned long long ull; ull orange[20001], dp[20001]; int mai..

문제 백준 2098번 풀이 DP 점화식을 $ dp[i][j] = i\ 정점에\ 방문했을\ 때\ j\ 정점들에\ 방문한\ 경우의\ 최솟값 $ 이라고 두겠습니다. $ j $만큼 방문했다는 것은 어떤 정점들에 방문했는지에 대해서 기록해둔다는 의미입니다. 이 $ j $를 비트마스킹을 사용하여 처리할 것입니다. 일반적인 vector 등을 사용하여 처리할 수도 있지만, vector를 매번 재귀 함수의 매개변수로 넘겨주기에는 cost가 작지 않기 때문입니다. $ j $를 이진수 정수로 두고 숫자 읽듯이 오른쪽부터 왼쪽 순서대로 읽을 겁니다. 그러면, 0번째 자리는 0번 정점에 방문했는지, 1번째 자리는 1번 정점에 방문했는지.. $ k $번째 자리는 $ k $번 정점에 방문했는지에 대한 정보를 담을 수 있습니다. 예..

문제 백준 2406번 풀이 최소 스패닝 트리를 구하는 것을 복잡하게 꼬와서 문제에 적어둔 문제입니다. $ 2, 3, 4, ..., N $번 컴퓨터가 모두 지사의 컴퓨터이고 이 컴퓨터들은 본사 컴퓨터(1번)과 연결되어있는 상태입니다. 문제에서 모든 컴퓨터들이 2개 이상의 간선으로 연결되어야 안정적인 네트워크라고 합니다. 이미 본사 컴퓨터들과는 모두 연결되어 있으니, 본사 컴퓨터를 제외하면 $ 2, 3, 4, ..., N $번 컴퓨터끼리 모두 연결하라는 문제로 볼 수 있습니다. 최소한의 비용으로 $ 2, 3, 4, ..., N $번 컴퓨터를 연결하는 것은 크루스칼 알고리즘을 사용하여 MST를 구하는 문제로 볼 수 있습니다. 크루스칼 알고리즘을 돌리는데 $ O(NlogN) $, 정렬을 하는데는 $ O(N^2l..

문제 백준 12024번 풀이 DFS로 짜면 TLE가 나니 다른 방법을 고려해야 합니다. $ i $, $ j $가 정해져있고, $ k_{1} $과 $ k_{2} $가 $ i $와 $ j $를 제외한 서로 다른 임의의 정점이라고 두겠습니다. $ i \to k_{1} $, $ k_{1} \to j $ 로 가는 방법이 있다고 하면 $ i $에서 $ j $로 가는 경로가 있다는 말과 같습니다. 반대로, $ j \to i $로 가는 간선도 있어야 합니다. $ j \to k_{2} $, $ k_{2} \to i $ 를 통해서 가는 방법이 있다면, 이 역시 $ j $에서 $ i $로 가는 경로가 있다는 말과 같습니다. $ i \to j \to i $로 가는 과정이 한가지 경우의 수가 됩니다. 또한, 문제에서 양방향(무..

문제 백준 17469번 코드업 3273번 풀이 Union-Find 자료구조를 사용하여 트리를 관리해줍니다. UF 자료구조 특성상 간선을 제거하는데 상당히 느립니다. 입력을 다 받고 이를 거꾸로 봐주면서 쿼리를 처리하면, 간선을 제거하는 것이 아니라 합치는 연산으로 볼 수 있습니다. 이를 합쳐주면서 "색깔"이라는 요소를 같이 관리해야 합니다. 색깔의 개수를 출력할 때는 중복되는 요소가 없어야 하니 set을 사용하면 될 것 같습니다. 여기서 백준 13306번 트리와는 다른 테크닉이 하나 더 필요합니다. small to large입니다. Union by rank와 유사하게 간선을 합치는 연산을 처리할 때, set 역시 합치는 연산을 할 것 입니다. 이 set을 작은 것에서 큰쪽으로 옮겨주면 모든 원소가 최대 ..