[BOJ]15954 인형들 - python

https://www.acmicpc.net/problem/15954

단순한 완전탐색으로 해결했습니다.

처음에 제출할때는 문제의 조건을 하나 놓쳐서 틀렸는데 주어진 조건이 K이상의 연속된 위치에 인형들을 선택하는것인데

K이상 이라는 조건을 놓쳐서 코드를 수정했다.

처음에 백준 사이트에 제출할때 python3로 제출했을때는 시간 초과가 났었는데 pypy3로 제출하니 시간초과가 발생하지 않고 통과되었다.

해당 문제의 FAQ를 정리한 글이 있어서 이를 참고하여서 문제를 해결했다.

https://www.acmicpc.net/board/view/29582

코드는 다음과 같다

import sys
import math
from decimal import *
 
fastinput = lambda: sys.stdin.readline().rstrip()
 
n, K = map(int, fastinput().split())
 
preference = list(map(int, fastinput().split()))
 
 
def distribute(m, list):
    result = 0
 
    for i in list:
        result += (i-m)**2
    return result/len(list)
 
 
resultCandidate = list()
 
for i in range(n-K+1):
    for j in range(n-K-i+2):
        tmp = preference[i:i + K + j]
        m = sum(tmp) / len(tmp)
        dis = distribute(m, tmp)
        resultCandidate.append(dis)
 
result = min(resultCandidate)
 
print(math.sqrt(result))