문제 백준 1240번 풀이 나가는 간선의 개수가 $ N - 1 $이고, 정점의 개수가 $ N $이므로 SPFA를 통해 구현하는 경우 최악의 시간 복잡도는 $ O(N^2) $이 됩니다. 테스트케이스의 개수가 $ M (\leq 1000) $이므로 최악의 경우 $ O(MN^2) $이 되어 TLE가 날 것 같이 생겼습니다. 하지만, 같은 그래프에 대해서 그러한 최악의 경우가 $ M $개가 되는 경우는 없다는 믿음을 가지고 SPFA를 사용하여 구현해봅시다. 16ms에 AC가 나오는 것을 볼 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pai..

문제 백준 1083번 풀이 그리디 문제입니다. $ i $를 $ 1 $부터 $ N $까지 순서대로 순회하면서, $ i $번째에 가능한 수 중 가장 큰 수를 넣어야 합니다. 모든 $ i ( 1 \leq i \leq N) $에 대하여 구간 $ [i, min(i + S, N)] $에 속하는 값 중 최댓값을 $ i $번째에 가져다 놓으면 됩니다. ($ S $는 사용한만큼 감소시킴) $ N $의 범위가 50이므로, 막구현해도 TLE가 나지는 않습니다. 다만, 탐색 범위를 한번 더 확인해서 런타임 에러를 주의할 필요는 있습니다. 소스코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.t..

문제 백준 1737번 풀이 기본적인 피보나치 문제도 DP이기 때문에, DP를 사용하는 문제임에는 쉽게 알 수 있습니다. 다만, 소수점 오차 때문에 dp table을 잡기가 조금 애매합니다. 소수점 오차를 줄이기 위해서 $ n $에서 뺄 1의 개수와 $ \pi $의 개수를 기록하여 dp table을 채우면 될 것 같습니다. $ dp[i][j] = f(n - i - \pi j) $라고 두고 재귀 함수로 풀었습니다. (단, $ f $는 Pibonacci 함수) 소스코드 #include using namespace std; typedef unsigned long long ull; ull MOD = 1000000000000000000; ull dp[1001][1001]; long double n; ull solv..

문제 백준 16074번 풀이 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로에서 방문하는 정점 중 최대 높이를 최소화하여야 합니다. $ Q = 1 $이라고 가정하면, 높이가 $ mid $보다 작은 정점들만 사용하여 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로가 있는가 에 대한 결정 문제를 풀어야 합니다. Union-Find 자료구조를 사용하여 $ mid $보다 작은 정점들을 순서대로 합쳐주는 것은 유사 크루스칼 알고리즘을 돌려 결정 문제를 해결할 수 있습니다. 높이 $ H $에 대한 이분 탐색 $ O(log H) $, 총 정점의 개수가 $ MN $이므로 유사 크루스칼 알고리즘을 돌리는데 $ O(MNlogMN) $이 걸립니다. 쿼리..

문제 백준 9694번 풀이 0번 정점(한신이)부터 최고의원을 만나기까지 친밀도의 합을 최소화하려면 최단 경로를 구하는 알고리즘을 사용하면 됩니다. 0번 정점을 시작 정점으로 잡아두고 다익스트라를 돌려주고, 각 정점을 갱신할 때마다 방문했던 정점들을 업데이트하면 쉽게 풀 수 있습니다. $ T $가 $ 100 $ 미만이고 $ N $이 $ 20 $ 이하이므로 플로이드-워셜(Floyd-Warshall)을 사용하더라도 $ O(TN^3) $에 풀릴 것 같습니다. 소스코드 #include using namespace std; typedef pair pii; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int t; cin >> t; for (int i = 1;..

문제 백준 15976번 풀이 문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다. $ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다. 문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다. 누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다. 문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께..