출처 : 반크 독도 포스터
문제]
Every day, as part of her walk around the farm, Bessie the cow visits her favorite, which has N flowers (all colorful daisies) labeled 1...N lined up in a row(1≤N≤100) . Flower i has pi petals (1≤pi≤1000).
As a budding photographer, Bessie decides to take several photos of these flowers. In particular, for every pair of flowers (i,j) satisfying 1≤i≤j≤N, Bessie takes a photo of all flowers from flower i to flower j (including i and j).
Bessie later looks at these photos and notices that some of these photos have an "average flower" -- a flower that has P petals, where P is the exact average number of petals among all flowers in the photo.
How many of Bessie's photos have an average flower?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N. The second line contains N space-separated integers p1…pN.
OUTPUT FORMAT (print output to the terminal / stdout):
Please print out the number of photos that have an average flower.
SAMPLE INPUT:
4
1 1 2 3
SAMPLE OUTPUT:
6
Every picture containing just a single flower contributes to the count (there are four of these in the example). Also, the (i,j) ranges (1,2) and (2,4) in this example correspond to pictures that have an average flower.
Problem credits: Nick Wu
참고풀이]
#include <stdio.h>
#include <stdlib.h>//malloc(), free()
int main(){
int N;//입력자료 수
int i,j,k;//반복변수
int cnt;//사진수를 세는 변수
int chk;//sum여부 체크 변수
int tot;//구역합 변수
//개수를 입력받는다.
scanf("%d",&N);
if(N>=1 && N<=100)
{
//N만큼의 동적 메모리를 선언한다.
int *M=(int *)malloc(sizeof(int)*N);
//선언된 메모리에 계산할 자료를 입력받는다.
for(i=0;i<N;i++)
{
scanf("%d",&M[i]);
if(M[i]<1 || M[i]>1000) return 0;
}
//꽃잎수를 구한다.
cnt=0;
for(i=0;i<N;i++)
{
for(j=i;j<N;j++)
{
//i~j까지의 꽃잎의 합을 구한다.
tot=0;
for(k=i;k<=j;k++)
tot += M[k];
//i~j까지의 꽃잎의 합이 영역 각 위치의 각값과 j-i+1 곱한 값과 같다면
//꽃 잎이 있는 것이므로 카운트를 센다.
chk=0;
for(k=i;k<=j;k++)
{
if(M[k]*(j-i+1)==tot)
{
chk=1;
break;
}
}
if(chk) cnt++;
}
}
//결과출력
printf("%d\n",cnt);
free(M);
}
return 0;
}
참고풀이 결과]
대한민국의 아름다운 영토, 독도
'프로그램 > C언어 1000제' 카테고리의 다른 글
C언어 14제] C언어 콘서트 CHAPTER 6 p217 도전문제 (2) (0) | 2021.11.22 |
---|---|
C언어 13제] C언어 콘서트 CHAPTER 6 p217 도전문제 (1) (0) | 2021.11.22 |
C언어 11제] USACO 2020 DECEMBER CONTEST, BRONZE PROBLEM 1. DO YOU KNOW YOUR ABCS? (0) | 2021.10.11 |
C언어 10제] 2015년 한국정보올림피아드 시˙도 지역본선 초등부 문제. 쇠막대기 (0) | 2021.10.04 |
C언어 9제] 깊이 우선 탐색(DFS) 이용한 프로그램 구현하기 (0) | 2021.09.30 |
댓글