문제 백준 15918번 풀이 $ x $와 $ y $ 자리가 주어집니다. 문제에서 같은 수는 수열에서 "2번" 나오고, 같은 수 ($ k $) 사이의 원소 개수가 $ k $가 된다고 하였으니, $ x $와 $ y $ 자리에 넣을 수는 $ y - x + 1 $로 정해집니다. 나머지 수를 채우는 방법은 dfs를 사용하여 $ 2^(12) $만큼 돌면서 조건에 맞게 수열을 채워주면 됩니다. 시간 복잡도는 $ O(2^N) $이 됩니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll;..

문제 백준 1644번 풀이 에라토스테네스 체를 사용하여 구간 $[2, N]$ 사이의 모든 소수를 구해줍니다. 구한 소수를 배열에 오름차순으로 두고, 그 배열의 길이를 $ K $로 둡니다. 어떤 구간이 $ N $이 되는지 찾아봅시다. 첫번째로는 누적합을 사용하여 모든 $ i, j (1 \leq i \leq j \leq N) $에 방문하여 $ psum[j] - psum[i] = N$인지 확인해주면 $ O(K^2) $에 가능합니다. 하지만, $ N $의 범위가 $ 4,000,000 $이므로 $ K $가 $ 10,000 $을 넘어가서 제곱 풀이는 사용할 수 없습니다. 누적합에서는 모든 $i, j$를 방문하지만, 투포인터로 가능한 $i, j$만 빠르게 탐색할 수 있습니다. 투포인터의 왼쪽 포인터를 $ L $, 오..

문제 백준 20312번 풀이 CPU $ i + 1$번째의 $ j $행은 CPU $ i $번째 $ j $행의 $ m_{i} $배 입니다. 따라서, $ i + 1 $번째 CPU 행의 합 = ($ i $번째 CPU 행의 합 + 1) * $ m_{i} $이 됩니다. 이전 행의 값을 계산해두면, 하나를 구할 때 $ O(1) $이므로, 모두 다 구해주는데 $ O(N) $이 걸리겠네요. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef v..

문제 백준 5052번 풀이 문자열 $ A $가 다른 문자열의 접두사인지 빠르게 확인해야 합니다. 입력 받은 전화번호를 모두 정렬해봅시다. 911 97625999 91125426 이 케이스를 정렬하면 911 91125426 97625999 이렇게 됩니다. 여기서 관찰할 수 있는 것은, 문자열 $ A $가 임의의 문자열 $ B $의 접두사가 된다면, 그러한 문자열 $ B $는 항상 $ A $ 바로 뒤에 있다는 것입니다. 이 말이 이해가 안된다면 사전을 생각해봅시다. "abcd", "abcde"와 같은 단어가 있다고 가정합시다. 이를 사전순으로 배열하면 "abcd"까지 같으니 더 긴 문자열이 뒤로 오게 됩니다. 그렇게 뒤에 온 문자열은 항상 앞의 문자열을 접두사로 포함하고 있는 꼴이 될 것 입니다. 마지막으로..

문제 백준 5578번 풀이 다른 문제와 달리 연결된 얼음의 넓이를 구하는 것이 아니라, 한번씩만 지나갈 수 있을 때 얼음을 최대한 많이 밟아야 합니다. 맵의 크기가 작기 때문에 DFS를 사용하여 완전 탐색을 하면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; int mp[91][91], ans, n, m; vector mv = { {-1, 0}, {0, -1}, {1, 0}, {0, 1}, }; int dfs(int x, int y) { int c = 0..

문제 백준 2146번 풀이 임의의 섬 하나를 지정합니다. 그리고, 그 섬의 테두리를 계속 한칸씩 늘려줍니다. 테스트케이스의 경우, 왼쪽 윗 섬을 잡고, 길이를 1씩 늘리면 위와 같은 모양이 됩니다. 계속해서 길이를 2로 늘려주면, 위와 같이 됩니다. 마지막으로 길이가 3이 되면, 다른 섬과 닿게 됩니다. 위 과정은 너비 우선 탐색, BFS로 해결할 수 있습니다. 이러한 과정을 나머지 섬에도 모두 해주면서 답을 갱신해주면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vect..