[코드트리] 특정 구간의 원소 평균값 / 완전 탐색

 

 

https://www.codetree.ai/missions/5/problems/elemental-mean-value-for-a-particular-interval?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

특정 구간의 원소 평균값

---

N개의 숫자가 주어지고, 특정 구간을 잡았을 때 그 구간 안에 있는 원소들의 평균값이 그 구간의 원소 중 하나가 되는 서로 다른 가짓수를 구하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 N이 주어집니다.

두 번째 줄에는 N개의 숫자가 공백을 사이에 두고 주어집니다.

• 1 ≤ N ≤ 100
• 1 ≤ 원소의 값 ≤ 1,000

출력 형식

첫 번째 줄에 가능한 서로 다른 가짓수를 출력합니다

 

입출력 예제

예제1

입력:

4
1 1 2 3

 

출력: 

6

 

예제 설명

구간 [1, 1], [2, 2], [3, 3], [4, 4]는 구간 안에 원소가 하나밖에 없으므로 평균이 곧 그 원소가 되기 때문에 조건을 만족하게 됩니다.

구간 [1, 2]에서는 평균이 1이며 구간 [1, 2] 내에 원소 1이 있기 때문에 조건을 만족합니다.

구간 [2, 4]에서는 평균이 2이며 구간 [2, 4] 내에 원소 2가 있기 때문에 조건을 만족합니다.

따라서 총 6개의 구간이 조건을 만족시킵니다.

 

 

---

내가 짠 코드

---

 

문제의 특성을 정리해보면 구간의 길이가 정해져 있지 않고 배열에서 구간을 잡으며 답이 되는 구간들의 수를 출력해야 한다.

따라서, 

우선 시작점과 끝점을 잡기 위한 루프를 실행한다.

#시작점 잡음 범위 [0, n)

for i in range(n): 

    # 끝점 잡음 끝점은 시작점보다 나중이므로 i부터 n까지이다.

     for j in rnage(i, n):

            #구간을 i부터 j까지로 하여 합을 구한 후 평균을 구한다.

            for k in range(i, j+1):

                    sum += arr[k];

            avg = sum / (j+1-i);

            # 구간을 한번 더 돌면서 평균과 같은 값이 있다면 불린 값을 true 로 변경한다.

           # 한번의 순회가 끝나면 불린값이 true 이면 카운팅한다.

 

#이 과정은 구간의 시작점과 끝점을 정하는 완전탐색 진행을 통해 쉽게 구현이 가능

n = int(input())

arr =list(map(int, input().split()))

avg = 0
sum = 0
cnt = 0
#시작점 잡음
for i in range(n):
    #끝점 잡음
    for j in range(i, n):
        ex = False
        sum = 0
        avg = 0
        for k in range(i, j+1):
            sum += arr[k]
        avg = sum /(j+1-i)
        for k in range(i, j+1):
            if avg == arr[k]:
                ex = True
        
        if(ex):
            cnt += 1
        

print(cnt)