on
C언어 6제] 2021년 한국정보올림피아드 1차대회 초등부 2. 나누기
C언어 6제] 2021년 한국정보올림피아드 1차대회 초등부 2. 나누기
출처 : 반크 카드뉴스
문제]
N개의 정수 수열 A1, A2,..., AN이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또 각 부분의 합은 모두 같아야 한다. 즉 어떤 i, j, k(1≤i＜j＜k＜N)에 대해서 [A1,...,Ai], [Ai+1,...,Aj], [Aj+1,...Ak], [Ak+1,...AN]으로 나눈다.
예를 들어 주어진 수열이 4, -1, 2, 1, -3, 1, 2, 2, 1, 3이라고 하자.
이 수열을 아래과 같이 나누면 각 부분의 합이 달라서 허용되는 형태가 아니다.
[4, -1, 2], [1, -3, 1, 2], [2, 1], [3]
아래와 같이 나눈 경우 각 부분의 합이 모두 같다.
[4, -1], [2, 1],[-3, 1, 2, 2, 1], [3]
아래과 같이 나눈 경우들도 각 부분의 합이 모두 같다.
[4, -1], [2, 1, -3, 1, 2], [2, 1], [3]
혹은 [4, -1, 2, 1, -3], [1, 2], [2, 1], [3]
수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.
제약 조건]
▶ 4 ≤ N ≤ 100000
▶ 1 ≤ i ≤ N에 대해 -1000 ≤ Ai ≤ 1000
입력 형식]
첫 번째 줄에 수열의 길이 N이 주어진다.
두 번째 줄에 N개의 정수 A1, A2, ... ,AN이 공배 하나씩을 사이로 두고 주어진다.
출력 형식]
첫 번째 줄에 가능한 방법의 개수를 출력한다.
출력값이 매우 클 수 있으므로 C, C++ 언어에서는 long long형의 변수를, Java에서는 long형의 변수를 사용해야 한다.
입력 예제1]
4
1 1 1 1
출력 예제1]
1
입력 예제2]
10
4 -1 2 1 -3 1 2 2 1 3
출력 예제2]
3
출처]
2021년 한국정보올림피아드 1차대회 2교시 초등부pdf
참고풀이]
#include
#include //malloc(), free()
int main()
{
int N;//수열의 길이 입력변수
int i,j;//반복변수
long long int Sum;//수열의 전체 합을 구하는 변수
//N개의 수열을 4파트로 나눌 수 있도록한다.
//파트당 최소 1개의 수열이 있도록 한다.
int Pn[4]={1,0,0,0};
//각각의 파트의 공통합을 구하기 위하여
//초기값을 0으로 셋팅한다.
long long int Psum=0;
//수열의 길이를 입력받는다.
//수열의 길이 범위는 4<=N<=100000이다.
scanf("%d",&N;);
if(N>=4 && N<=100000)
{
//N개의 값을 입력받는다. 동적메모리 활용한다.
int *M=(int *)malloc(sizeof(int)*N);
for(i=0;i
{
scanf("%d",&M;[i]);
//1~N개의 수열중 -1000~1000범위 값이 아니면 작업을 끝낸다.
if(M[i]<-1000 || M[i]>1000) return 0;
}
//수열의 전체 합을 구한다.
Sum=0;
for(i=0;i
Sum+=(long long int)M[i];
//각 구역의 합이 같은 값을 구한다.
for(j=0;j
{
Psum+=(long long int)M[j];
for(i=3;i>=0;i--)
if(Psum==Sum*i/4)
Pn[i] += Pn[i-1];
}
//결과출력
printf("%d",Pn[3]);
//동적메모리를 해제한다.
free(M);
}
return 0;
}
참고풀이 결과]
대한민국의 아름다운 영토, 독도
from http://kmatter.tistory.com/124 by ccl(S) rewrite - 2021-09-14 07:01:42