🏆 문제 난이도- Platinum IV🔗 문제 링크https://www.acmicpc.net/problem/2618📝 문제 분석 & 접근이런 유형의 문제는 단순히 현재 사건에 대해 두 경찰차 중 더 가까운 차를 보내는 탐욕적(Greedy) 접근으로는 최적의 해를 찾을 수 없습니다.왜냐하면 당장 가까운 차를 보냈을 때, 다음 사건을 처리할 때 더 큰 손해를 볼 수 있기 때문입니다.따라서 동적 계획법을 이용해야 합니다.현재의 선택이 미래의 결과에 영향을 미치므로, 과거의 상태를 기억하고 최적의 선택을 이어가는 방식을 사용해야 문제를 풀 수 있습니다.✨ 핵심 아이디어사실 아이디어 자체는 매우 단순합니다.DP 상태 정의: dp[i][j] = 경찰차 1이 마지막으로 처리한 사건이 i, 경찰차 2가 마지막으로..

🏆 문제 난이도- Platinum V🔗 문제 링크https://www.acmicpc.net/problem/7578📝 문제 분석 & 접근아이디어는 간단합니다.A를 순서대로 순회하며, 같은 값을 가진 B의 index가 어딘지를 찾습니다.찾은 B index보다 뒤에 값들 중에 방문한 적이 있는지를 확인하고 전부 더합니다. (SegmentTree에서 Query 역할)방문한 적 없다면 겹치는 선이 없는 것입니다.SegmentTree Update를 통해서 방문한 노드와 해당 노드를 포함하는 노드들에 1을 더해줍니다.(새로운 노드에 방문했다는 의미로 1을 더해주는 것입니다.)2.에서 찾은 Sum 값들을 전부 더하고 출력합니다.💻 코드import java.io.StreamTokenizerlateinit var ..

🏆 문제 난이도- Platinum V🔗 문제 링크https://www.acmicpc.net/problem/13141📝 문제 분석 & 접근플레 치고는 어렵지 않은 문제입니다.플로이드-와샬 알고리즘을 사용해서 모든 정점 쌍 간의 최단 거리를 구해줍니다.플로이드-와샬을 사용하는 이유는, 모든 점에서 다른 모든 점들까지의 최단거리를 모두 구해야 하기 때문입니다. 각 노드의 최단거리를 구한 다음에는 각 정점 별로 타는데 가장 오래 걸리는 시간들 중에서 가장 작은 값을 구하면 됩니다.✨ 핵심 아이디어시작점 i에서 불이 붙기 시작해서 어떤 도로 j (start, end)를 태우는 데 걸리는 시간은 maxLength = dist[i][start] + dist[i][end] + length[j]로 계산할 수 있습니..

🏆 문제 난이도- Gold I🔗 문제 링크https://www.acmicpc.net/problem/2357📝 문제 분석 & 접근수열의 크기를 N, 질의의 수를 M이라고 할 때, 각 질의마다 O(N)의 시간이 걸리므로, 매번 순회하면서 최솟값과 최댓값을 찾으면 전체 시간 복잡도는 O(NM)이 될껍니다.즉, 최악의 경우 수열의 크기 최대 100,000 그리고 질의의 수 최대 100,000이므로 연산 횟수가 10^10이 될 수 있습니다.이처럼 많은 질의를 빠르게 처리해야 할 때는, 질의에 답하기 위해 미리 데이터를 가공해두는 효율적인 자료구조가 필요합니다.이 문제에 가장 적합한 자료구조는 바로 세그먼트 트리(Segment Tree)입니다 세그먼트 트리가 무엇인지는 따로 설명하지 않겠습니다만, 괜찮은 설명..

🏆 문제 난이도- Gold II🔗 문제 링크https://www.acmicpc.net/problem/15824📝 문제 분석 & 접근일단 모든 조합을 직접 만들어서 계산하는거는 불가합니다. 시간초과 이슈~따라서, 각 봉우리의 높이(값)가 전체 합에 얼마나 기여하는지를 따로 계산해서 더해주는 방식으로 접근해야 합니다.✨ 핵심 아이디어- 봉우리의 기여도 계산하기정렬된 배열에서 각 봉우리가 최대값이 되는 경우와 최소값이 되는 경우를 계산하여 전체 합에 더해줍니다.봉우리 arr[i]가 조합의 최대값이 되는 경우: arr[i]를 포함하고, arr[0]부터 arr[i-1]까지의 i개 봉우리들 중에서 나머지 봉우리를 선택해야 합니다. 즉, i개의 봉우리로 만들 수 있는 모든 조합의 수는 2^i개입니다. 따라서 a..

🏆 문제 난이도- Gold II🔗 문제 링크https://www.acmicpc.net/problem/13334📝 문제 분석 & 접근처음 문제를 접하면 모든 사람의 집과 회사 위치를 탐색해야 할 것 같아서 복잡하게 느껴질 수 있습니다.하지만 잘 생각해 보면, 기차 경로는 시작점과 끝점 사이의 거리가 d 이하인 모든 구간을 의미합니다.즉, [기차의 시작점, 기차의 시작점+d] 구간을 검사하면 되는 것입니다. 우리는 이 기차 구간 안에 최대한 많은 사람이 포함되도록 해야 합니다.한 사람이 기차에 타려면, 그 사람의 집과 회사 위치가 모두 이 구간 안에 포함되어야 합니다.✨ 핵심 아이디어단순히 1부터 끝까지 모든 구간을 하나씩 검사하는 것은 오랜 시간이 걸립니다.따라서 아래같은 약간의 트릭이 필요합니다. ..

🏆 문제 난이도- Gold III🔗 문제 링크https://www.acmicpc.net/problem/14725📝 문제 분석 & 접근 문제를 해결하기 위해 가장 먼저 떠올릴 수 있는 아이디어는 트리(Tree) 자료구조를 사용하는 것입니다.각 경로의 문자열을 트리의 노드로 삼아 연결하는 방식입니다루트 노드(Root Node): 개미굴의 시작점을 나타내는 가상의 루트 노드를 만듭니다.자식 노드(Child Nodes): 각 경로의 문자열은 부모 노드의 자식 노드가 됩니다.동일 경로: 만약 이미 존재하는 경로가 다시 입력으로 들어오면, 새로운 노드를 추가하는 대신 기존 노드를 따라가야 합니다.예를 들어, A -> B 경로가 추가된 후, 다시 A -> C 경로가 들어온다면, 루트 노드에서 A 노드를 찾고, ..

🏆 문제 난이도- Gold III🔗 문제 링크https://www.acmicpc.net/problem/2533📝 문제 분석 & 접근이 문제에서 각 노드는 사람을 나타내고, 간선은 친구 관계를 의미합니다.여기서 핵심 규칙은 모든 일반인 친구는 적어도 한 명의 얼리어답터 친구를 가지고 있어야 한다는 것입니다. 접근 방식트리 DP를 사용하기 위해, 각 노드(사람)에 대해 두 가지 상태를 정의하고, 그에 따른 최소 얼리어답터 수를 계산합니다.현재 노드가 얼리어답터인 경우: 현재 노드의 자식 노드는 얼리어답터이든 일반인이든 상관없습니다. 모든 자식 노드에 대해 '얼리어답터인 경우'와 '얼리어답터가 아닌 경우' 중 더 작은 값을 선택하여 더해줍니다.현재 노드가 얼리어답터가 아닌 경우: 문제의 규칙에 따라 모든..

🏆 문제 난이도- Platinum V🔗 문제 링크https://www.acmicpc.net/problem/2162📝 문제 분석 & 접근이 문제는 두 가지 개념적 큰 흐름이 있습니다.두 선분이 만나는지 판별하는 선분 교차 판정만나는 선분을 그룹으로 묶는 Union-Find코드의 전체적인 흐름은 아래와 같이 설계할 수 있습니다모든 선분 쌍에 대해 교차하는지 검사하기교차한다면 Union-Find로 두 선분을 같은 그룹으로 합치기모든 검사가 끝나고, Union-Find에 남아있는 그룹의 총 개수와 가장 큰 그룹의 크기 세기✨ 핵심 아이디어1. 선분 교차 판정 (CCW 알고리즘)두 선분이 교차하는지 판별하는 가장 대중적(?)인 방법은 CCW(Counter-Clockwise) 알고리즘입니다. CCW는 세 점의..

🏆 문제 난이도- Platinum V🔗 문제 링크https://www.acmicpc.net/problem/12850📝 문제 분석 & 접근이 문제의 경우 산책 시간 D 가 10억까지 가능해서, 단순 DFS/BFS로 풀 경우 제한시간 1초를 훌쩍 넘기게 됩니다.이를 해결하기 위해, 분할정복과 행렬의 곱으로 문제를 풀어야 합니다.우리는 D분 동안 길을 따라 걸었을 때, 출발지인 정보과학관에서 다시 정보과학관으로 돌아오는 경우의 수를 구해야 합니다.1분에 한 건물에서 인접한 다른 건물로 이동할 수 있다고 했으니, 결국 길이가 D인 경로의 수를 찾는 것과 같습니다. 이 문제를 그래프로 모델링해볼 수 있습니다.8개의 건물을 정점(Vertex)으로, 건물 사이의 길을 간선(Edge)으로 생각하는 거죠.그리고 이..