https://www.acmicpc.net/problem/21757
21757번: 나누기
$N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어
www.acmicpc.net
[난이도] Gold3
[유형] DP
[풀이]
나중에..
#include <cstdio> #include <cstring> using ll = long long; using namespace std; int N,sum[100001],base,cnt; ll dp[5]; int main(){ scanf("%d",&N); for(int i=1;i<=N;i++) { int v; scanf("%d",&v); sum[i]=sum[i-1]+v; if(sum[i]==0) cnt++; } if(sum[N]==0){ if(cnt<4) puts("0"); else printf("%lld",(ll)(cnt-1)*(cnt-2)*(cnt-3)/6); return 0; } if(sum[N]%4){ puts("0"); return 0; } base=sum[N]/4; dp[0]=1; for(int i=1;i<N;i++){ if(sum[i]%base) continue; int j=sum[i]/base; if(j==0 || j>3) continue; dp[j]+=dp[j-1]; } printf("%lld",dp[3]); }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/21757.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Bronze1] 21760 : 야구 시즌 (C++) (0) | 2022.07.05 |
|---|---|
| [BOJ/백준][Silver1] 21758 : 꿀 따기 (C++) (0) | 2022.07.04 |
| [BOJ/백준][Bronze2] 21756 : 지우개 (C++) (0) | 2022.07.04 |
| [BOJ/백준][Silver3] 19941 : 햄버거분배 (C++) (0) | 2022.07.04 |
| [BOJ/백준][Silver5] 19939 : 박 터뜨리기 (C++) (0) | 2022.07.04 |