문제 백준 13398번 풀이 그냥 연속한 수열에서 최댓값을 구하는 점화식은 $ dp[i] = max(dp[i] + arr[i], 0) $이라는 것을 알고 있습니다. ( ... ⓐ ) 여기 다른 dp 배열을 하나 더 만들어, 수를 한번 제거하였을 때의 최댓값도 같이 관리해줍니다. ( ... ⓑ ) 그러면, ⓐ의 DP 배열을 $ A $, ⓑ의 DP 배열을 $ B $라고 하면, $ A $는 위 점화식으로 쉽게 채워줄 수 있습니다. $ B = max(A[i - 1], B[i - 1] + arr[i]) $라는 점화식으로 나타낼 수 있습니다. $ A_i $까지 더한 합에서 $ i $만 제하는 경우 또는 $ B_i $에서(이미 한번 뺀 경우) 현재 값을 더해준 경우로 두 가지로 나뉘기 때문에 위와 같은 점화식이 나옵..

문제 백준 15487번 풀이 임의의 인덱스 $ a $를 기준으로 나누었다고 가정해봅시다. 이제 두 구간 $ [1, a] $에서 $ -A[i] + A[j] $의 최댓값과, $ (a, N] $에서 $ -A[l] + A[k] $의 최댓값을 구하면 됩니다. $ a $를 기준으로 왼쪽 구간의 최댓값의 배열과 오른쪽 구간의 최댓값의 배열을 각각 $ L, R $이라고 두면, 범위가 늘어날수록 최댓값이 점점 커지므로 투포인터 같은 DP로 $ L, R $을 $ O(N) $에 채워줄 수 있습니다. 그러면, 모든 $ i $에 대하여 $ L[i] + R[i + 1] $의 최댓값이 정답이 됩니다. (양쪽으로 나누는 기준점이 포함되면, 중복으로 선택될 수 있기 때문에 양쪽 중 하나에서는 빼야합니다.) 소스코드 #include #..

문제 백준 2904번 풀이 $A$를 나눌 수 있는 $X$는 $A$의 소인수를 의미합니다. 이 점을 유의해서 문제를 접근해봅시다. 연산을 잘 실행해준 뒤 각 수들의 최대공약수를 최대화하려면, 모든 수들의 소인수를 골고루 분배해주면 됩니다. 예를 들면, $2^5 \cdot 3^1$과 $2^1 \cdot 3^3 $라는 두 수가 있다고 생각해봅시다. 소인수 2는 총 6개, 3은 4개가 있습니다. 이제 위 소인수들을 골고루 분배하면, 각각의 수는 $2^3 \cdot 3^2$이 됩니다. 위 방법(모든 수의 소인수 개수를 세는 것)으로 최대공약수를 최대화할 수 있는데, 몇 번을 움직여야 하는지도 구해야합니다. 예를 들어서, $2^5 \cdot 3^1 \cdot 5^3$이라는 수가 있고, 위에서 구한 최대공약수가 $2..

문제 백준 9878번 풀이 이벤트 T와 D를 순서대로 처리해야 합니다. 이벤트 T와 D 각각에서는 작은 것부터 차례로 봐주면 되지만, T와 D 원소 각각에 대해서는 대소 관계를 정의하기는 어렵습니다. 하지만, 매번 T와 D 중에 가장 작은 원소끼리만 비교하여 현재 순간에서 이벤트 T가 먼저 오는지, D가 먼저 오는지 판별하여 처리해주는 것은 쉽습니다. 위 작업을 하기 위해서, 현재 시간과 현재 위치를 저장해두며 문제에서 시킨대로 하면 됩니다. 작은 것부터 봐주는 과정은 우선순위 큐, 나머지는 구현입니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long ..

문제 백준 14256번 풀이 $ SSR(A, B) = (\sqrt{A} + \sqrt{B}) ^ 2 $이 정수가 되어야 합니다. 식 정리를 해봅시다. $$ = A + B + 2 \cdot \sqrt{AB} $$ $A, B$는 이미 정수이므로, $ \sqrt{AB} $가 정수가 되면 됩니다. 따라서, $ AB $가 제곱수가 되면 됩니다. 이제, $ AB $가 제곱수가 되는 경우의 수를 모두 구하면 됩니다. $ A $를 고정시키고, 가능한 $ B $의 개수를 세봅시다. $ A $를 소인수 분해한 뒤, 지수가 홀수인 밑만 곱해준 수를 $ c $라고 정의합니다. 그러면, $ B $는 $ c \cdot k ^ 2 $이라고 둘 수 있습니다. ($k$는 임의의 정수) (왜냐하면, $B$가 항상 $c$의 배수여야 $ ..

문제 백준 16940번 풀이 이러한 트리를 BFS, 너비 우선 탐색으로 순회한 결과가 올바른 것인지 아닌지 출력해야 합니다. 이 과정이 올바르다면, 아래의 조건을 만족할 것입니다. 1) 각 노드의 깊이는 오름차순 형태이다. 2) 부모 노드가 들어온 순서대로 자식 노드들 간의 순서가 결정된다. 2번째 조건이 말로 하면 어려우니, 아래 예제를 참고해주세요. 위 예제 사진에서는, 깊이가 0(루트 노드)인 노드는 1, 깊이가 1인 노드는 2와 3, 깊이가 2인 노드는 4입니다. 아래와 같이 순회했다고 가정합시다. 1 2 3 4 1번째 조건에서, 각 노드들의 깊이를 배열로 나타내면, [0, 1, 1, 2]이므로 오름차순을 만족합니다. 2번째 조건에서, 각 노드들의 부모 노드는 (루트 노드 제외) [1, 1, 2]..