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 <stdio.h>
#include <stdlib.h> //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<N;i++)
      {
         scanf("%d",&M[i]);
         //1~N개의 수열중 -1000~1000범위 값이 아니면 작업을 끝낸다. 
         if(M[i]<-1000 || M[i]>1000) return 0;
      }

      //수열의 전체 합을 구한다.
      Sum=0;
      for(i=0;i<N;i++) 
         Sum+=(long long int)M[i];

      //각 구역의 합이 같은 값을 구한다.
      for(j=0;j<N;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;
}

 

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도