20651번 - Daisy Chains
매일 농장을 산책하는 소 베시(Bessie)는 자신이 가장 좋아하는 목초지에 들른다. 이 목초지에는 총 N 송이의 꽃(모두 알록달록한 데이지)이 일렬로 늘어서 있으며, 각 꽃에는 1부터 N까지 번호가 붙어 있다. 제약은 다음과 같다.
1 ≤ N ≤ 100
꽃 i는 pi개의 꽃잎을 가지고 있으며, 각 꽃잎 수에 대한 제한은 다음과 같다.
1 ≤ pi ≤ 1000
사진 찍는 것을 좋아하는 베시는 이 꽃들의 사진을 여러 장 찍기로 했다. 특히, 모든 쌍 (i, j)에 대하여
1 ≤ i ≤ j ≤ N
를 만족하는 경우마다, 베시는 꽃 i부터 꽃 j까지 (양 끝의 i와 j를 포함한) 모든 꽃을 한 장의 사진에 담아 찍는다.
나중에 베시는 찍은 사진들을 다시 보다가, 몇몇 사진에는 “평균 꽃(average flower)”이 존재한다는 사실을 알게 된다.
어떤 사진에 포함된 모든 꽃의 꽃잎 수의 평균을 P라고 하자. 이때 그 사진 안에 꽃잎 수가 정확히 P개인 꽃이 하나라도 존재하면, 그 사진은 평균 꽃을 가진 사진이라고 한다.
베시가 찍은 모든 사진들 중에서, 평균 꽃을 가진 사진은 총 몇 장인지 구하여라.
입력의 첫 번째 줄에는 정수 N이 주어진다. 두 번째 줄에는 N개의 정수 p1, p2, &dots;, pN 이 공백으로 구분되어 주어진다.
평균 꽃을 가지는 사진의 개수를 정수 하나로 출력한다.
4 1 1 2 3
6
하나의 꽃만 포함하는 사진은 항상 그 꽃이 평균 꽃이 되므로, 이 예제에서는 그런 사진이 총 4장 있다. 이외에 구간 (i, j)가 (1, 2), (2, 4)인 경우의 사진도 평균 꽃을 가진다.
댓글을 작성하려면 로그인해야 합니다.
wisekee2 1년 전 1
문제
매일 농장을 산책하는 소 베시(Bessie)는 자신이 가장 좋아하는 목초지에 들른다. 이 목초지에는 총 N 송이의 꽃(모두 알록달록한 데이지)이 일렬로 늘어서 있으며, 각 꽃에는 1부터 N까지 번호가 붙어 있다. 제약은 다음과 같다.
1 ≤ N ≤ 100
꽃 i는 pi개의 꽃잎을 가지고 있으며, 각 꽃잎 수에 대한 제한은 다음과 같다.
1 ≤ pi ≤ 1000
사진 찍는 것을 좋아하는 베시는 이 꽃들의 사진을 여러 장 찍기로 했다. 특히, 모든 쌍 (i, j)에 대하여
1 ≤ i ≤ j ≤ N
를 만족하는 경우마다, 베시는 꽃 i부터 꽃 j까지 (양 끝의 i와 j를 포함한) 모든 꽃을 한 장의 사진에 담아 찍는다.
나중에 베시는 찍은 사진들을 다시 보다가, 몇몇 사진에는 “평균 꽃(average flower)”이 존재한다는 사실을 알게 된다.
어떤 사진에 포함된 모든 꽃의 꽃잎 수의 평균을 P라고 하자. 이때 그 사진 안에 꽃잎 수가 정확히 P개인 꽃이 하나라도 존재하면, 그 사진은 평균 꽃을 가진 사진이라고 한다.
베시가 찍은 모든 사진들 중에서, 평균 꽃을 가진 사진은 총 몇 장인지 구하여라.
입력
입력의 첫 번째 줄에는 정수 N이 주어진다.
두 번째 줄에는 N개의 정수 p1, p2, &dots;, pN 이 공백으로 구분되어 주어진다.
출력
평균 꽃을 가지는 사진의 개수를 정수 하나로 출력한다.
예제 입력 1
예제 출력 1
예제 설명
하나의 꽃만 포함하는 사진은 항상 그 꽃이 평균 꽃이 되므로, 이 예제에서는 그런 사진이 총 4장 있다.
이외에 구간 (i, j)가 (1, 2), (2, 4)인 경우의 사진도 평균 꽃을 가진다.