문제 백준 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 $에서(이미 한번 뺀 경우) 현재 값을 더해준 경우로 두 가지로 나뉘기 때문에 위와 같은 점화식이 나옵..

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

문제 백준 2201번 풀이 길이가 $ 1, 2, 3, 4, 5 $인 이친수들을 모두 적어보겠습니다. $ 1 $ $ 10 $ $ 100, 101 $ $ 1000, 1001, 1010 $ $ 10000, 10001, 10010, 10100, 10101 $ 이며 각각의 개수는 $ 1, 1, 2, 3, 5 $와 같습니다. 대충 규칙이 피보나치 수열과 같다는 것을 볼 수 있습니다. 길이가 $K$인 이친수의 개수가 피보나치 수열의 원소와 같다는 믿음을 가지면 아래 문제를 푸는 것으로 바꿀 수 있습니다. $N$번째 이친수의 길이는 몇인가? 이는 피보나치 수열을 한번 돌리면 길이를 구할 수 있습니다. 다음은, 길이가 $ K ( K \geq 2) $인 경우 이친수는 "항상" 앞이 10으로 시작합니다. (이친수의 시작은 ..