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 |