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

1번은 간단한 dfs 문제입니다. 단방향 그래프이므로 진입 차수가 0인 정점부터 시작한 뒤 결과를 출력하면 됩니다. 2번은 간단한 dp 문제입니다. 3번은 크기가 고정되어 있으므로 슬라이딩 윈도우를 사용하면 됩니다. 4번은 간단한 dfs 문제입니다. 5번은 map 자료구조를 사용하면 됩니다. 6번은 기본적인 아이디어는 분할 정복입니다. N 제한이 작아서 최댓값을 구할 때 세그먼트 트리가 필수는 아닙니다. 7번은 SQL join, where 등을 적절히 사용하면 쉽게 풀립니다. 8번은 css selector와 media query의 개념만 있으면 쉽게 풀 수 있습니다. 작년에 비해서 알고리즘 문제의 전체적인 평균 난이도는 오른 것 같은데, 어려운 문제는 없었습니다. 대부분 솔브드 실버 중위권에서 상위권인 ..

문제 백준 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$의 배수여야 $ ..