본문 바로가기

DP37

백준 21909 / C++ https://www.acmicpc.net/problem/21909 21909번: Divisible by 3 For an array $[b_1, b_2, \dots , b_m]$ of integers, let’s define its weight as the sum of pairwise products of its elements, namely as the sum of $b_ib_j$ over $1 \le i < j \le m$. You are given an array of $n$ integers $[a_1, a_2, \dots , a_n]$, and a www.acmicpc.net [ 풀이 ] 문제의 정의에 나온 weight는 식으로 정리하면, 1/2*{(a[l]+....+a[r])^2 - (a[l]^.. 2022. 8. 1.
백준 21757 / C++ https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net [ 풀이 ] dp[i][j]를 i번째 인덱스까지 j개로 분할하는 방법의 수라고 놓자. 상태전이 시켜보자. i번을 안쓰는 경우 그냥 dp[i+1][j]로 넘어간다. i번을 사용하는 경우 dp[i+1][j+1]로 넘어간다. 사용할 수 있는 경우는 문제조건에 따라 잘 체크하면 된다. 그리고 매번 i번에서 i+1만 참조하므로 토글링으로 공간복잡도를 조금 줄여줄 수 있다. .. 2022. 8. 1.
백준 15560 / C++ https://www.acmicpc.net/problem/15560 15560번: 구간 합 최대? 1 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 103, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. ( - 102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼 www.acmicpc.net [ 풀이 ] 식을 정돈하자. 누적합 psum으로 정리하면.. U*(psum[j]-psum[i-1])+V(j-i)이다. 왠지 U*psum[i]+V*i 를 다시 f(i)로 놓고 싶다. 그러면 식은 f(j)-f(i-1)-V가 된다. 이제 문제는 구간 [A,B]에서 f(j)-f(i-1)의 최댓값을 구하면 된다. O(N)에 해결하자. dp[j]를 f(j)-f(i.. 2022. 8. 1.
dp with 포함배제 원리 포함배제 원리를 이용하는 dp문제 2개를 풀어보자. 1. BOJ 14517 https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net [ 풀이 ] 문제를 잘 이해해야 한다. 부분수열이므로 연속된 팰린드롬일 필요가 없다. 맨처음과 끝에서 시작해서 좁혀가면서 갱신해주면 된다. dp[s][e]:=구간 [s,e]를 볼 때 팰린드롬의 총 개수라고 정의하면, 상태전이는 3가지가 있다. 1. s를 사.. 2022. 8. 1.

티스토리툴바