문제 백준 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..

문제 백준 20309번 풀이 길이가 3이 되도록 연속된 구간을 잡아서 reverse해서 배열을 오름차순으로 만들어야 합니다. [a, b, c]라면 [c, b, a]가 됩니다. 조금 관찰하면, 중간의 수는 고정되있고 양끝의 수만 바뀌는 것을 볼 수 있습니다. 이를 이용하면, 홀수 자리에는 홀수만, 짝수 자리에 짝수만 오면 몇번이던 실행하여 정렬할 수 있습니다. 하지만 짝수 자리에 홀수(또는 홀수 자리에 짝수)가 오게 된다면 몇번 실행하던 홀수 자리에 있던 짝수가 짝수 자리로 갈 수 없습니다. 예를 들면, [2, 1, 3]과 같은 배열이 있는데 이 배열은 몇번이고 트리플 소트를 실행하더라도 1이 첫번째 자리로 갈 수 없습니다. 따라서, 짝수 자리에는 짝수만, 홀수 자리에 홀수만 오는지 확인해주면 됩니다. 소..

문제 백준 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..

문제 백준 2662번 풀이 전형적인 DP 문제입니다. $ dp[i][cost] = "$ $ i $번째 회사까지 $ cost $원을 사용했을 때 최대 이익금" 이라고 점화식을 세웁니다. 회사 하나를 늘릴 때마다 어떤 cost ($ 1 \leq cost \leq N $)를 고정시키고, prev ($ 1 \leq prev \leq cost $) 를 순회해주며 DP Table을 채워줍시다. 역추적은 $ dp[i][cost] $가 최댓값을 가질 때의 $ prev $의 값을 저장해두면서 $ dp[i - 1][prev] $... 이런식으로 역추적해나가면 됩니다. 시간 복잡도는 $ O(N^3) $이 됩니다. 소스코드 #include using namespace std; typedef long long ll; typed..