[USACO] Daisy Chains (C언어)

www.acmicpc.net/problem/20651

문제는 백준 사이트에서 풀었다.

20651번: Daisy Chains

<문제해설>

처음엔 문제를 이해하는게 어려웠다...

꽃들이 한줄로 늘어져있고 사진을 찍는다.
사진 한장에는 꽃이 한송이만 있을수도 있고, 여러송이가 있을 수 있다.
사진속 꽃들의 꽃잎 갯수를 이용해서 그 사진의 평균 꽃잎을 구한다.
ex ) 사진 한장에 꽃이 3송이 찍혀있고 꽃잎의 갯수가 각각 1,2,3 이라면
     그 사진의 평균 꽃잎은 (1+2+3) / 3 해서 2 가 된다.
해당 사진이 평균 꽃잎에 해당하는 꽃을 가지고 있다면 그 사진을 카운트한다.
이렇게 총 몇장의 사진이 카운트 되는지를 출력하는 문제이다.

<풀이>

우선 모든 사진을 찍어보자.
꽃이 한송이, 두송이, 세송이... 사진 한장에 최대 몇개의 꽃을 찍을지 정하고, 시작점을 정한다.
모든 사진을 찍는건 되었으니,
각 사진마다 평균 꽃잎을 구하고, 평균꽃잎을 가진 꽃이 있는지 체크한다.

추가적인 설명은 아래 코드에 주석으로 달아두었다.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int arr[100];
    int n;
    scanf("%d", &n);

    for(int i = 0 ; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int tempSum;
    int tempAvg;
    int tempCnt;
    int answer = 0;

    for(int i = 1; i <= n; ++i){ //사진 한장에 꽃 최대 몇개 ? i 개
        for(int begin = 0 ; begin <= n-i; ++begin){   //사진의 꽃 시작점은 0 ~ n-i
            tempSum = 0;
            tempCnt = 0;
            tempAvg = 0;
            for(int j = begin; j < begin + i; j++){ //시작점 부터 사진 내 꽃 갯수만큼
                tempSum += arr[j];
            }
            if(tempSum % i != 0) { continue; }  //평균 꽃잎이 소수점 나오면 continue
            tempAvg = tempSum / i;
            for(int j = begin; j < begin + i; j++){//사진에서 avg flower 존재하면 ? 카운트
                if(arr[j] == tempAvg){
                    ++tempCnt;
                    break;
                }
            }
            answer += tempCnt;
        }
    }

    printf("%d", answer);

}