본문 바로가기

누적합14

백준 5463 / C++ https://www.acmicpc.net/problem/5463 5463번: 건포도 플로브디브의 유명한 초콜릿 가공업자 Bonny는 가로 M개, 세로 N개의 격자에 건포도들이 들어있는, N*M크기의 건포도 초콜릿을 만들었다. 각 1*1 격자에는 최소 1개 이상의 건포도가 들어있으며, 2개 www.acmicpc.net [ 풀이 ] 나눴을 때 합을 계산해주려면 시작점 좌표와 끝점 좌표를 알아야 한다. 마침 n,m도 50이하다. dp[sx][sy][ex][ey]를 (sx,sy)~(ex,ey)로 만들어지는 직사각형에서 건포도의 최소 양이라고 하자. 전이는 2가지다. 가로로 자르는 경우, 세로로 자르는 경우. 이후 식을 세우는건 쉬우므로 코드로 대체한다. [ Code ] #include using namespa.. 2022. 8. 17.
백준 12911 / C++ https://www.acmicpc.net/problem/12911 12911번: 좋아하는 배열 첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] dp[i][j]를 길이 i이고 j로 끝나는 조건을 만족하는 개수라고 하자. 전체 경우의 수는 dp[N][1]+...+dp[N][K]가 된다. 문제조건의 여사건은 A가 B의 배수라는 것이다. 즉, 뒤로갈수록 앞의 약수가 되면 된다. WLOG 순서를 뒤집어서 뒤로 갈수록 앞의 배수가 되도록 해도 된다. dp[i+1][j]=dp[i][1]+....+dp[i][k]-sum(dp[i][u]) (u는 j의 배수) 임을 알 수 있다. S(i)=dp[i][1]+...+dp[i][k]라고 정.. 2022. 8. 12.
백준 3114 / C++ https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net [ 풀이 ] dp[i][j]를 (i,j)까지 왔을 때 합의 최댓값이라 하자. dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]에서 올 수 있다. 앞의 두 경우는 이전dp값에다 현재 (i,j)에서 위아래로 바나나와 사과개수를 더해주면 된다. 이미 각 열에 대한 바나나의 합과 사과의 합을 전처리해놓자. dp[i][j-1]에서 오는 경우는 만약 (i,j)가 사과였다면.. 2022. 8. 2.
백준 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.

티스토리툴바