글 읽기 - 파이썬 시간초과 해결을 못하겠어요 ㅠㅠ

llkpoi 3년 전 0

어디서 시간을 잡아먹었을까요
도와주세요 도무지 모르겠어요 ㅠㅠ

N, M = map(int, input().split())

A = list()  
for i in range(N):
        A.append(list(map(int, input().split())))

B = list()  # 모든치킨집의 좌표 
for i in range(N):
    for j in range(N):
        if A[i][j] == 2:
            B.append([i, j])

def chicken(C):     # 각 집과 M개의 치킨집중 거리의 최솟값의 합
    SUM = 0
    temp = 1000
    for i in range(N):
        for j in range(N):
            if A[i][j] == 1:
                for c in C:
                    a = c[0] - i
                    b = c[1] - j
                    if a < 0:
                        a = -a
                    if b < 0:
                        b = -b
                    temp = min(temp, (a + b))
                SUM += temp
                temp = 1000
            else:
                continue
    return SUM

C = list() #선택한 M개 치킨집의 좌표
D = list() # C의 각 경우마다 나오는 값의 리스트
def func(a): 
    # 모든치킨집에서 M개의 치킨집을 골라 chicken함수로 최솟값을구하여 D에넣음
    if len(C) == M:
        D.append(chicken(C))
        return 
    else:
        for b in range(a, len(B)):
            C.append(B[b])
            func(a + 1)
            C.pop()
func(0)
print(min(D))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 해결을 못하겠어요 ㅠㅠ

llkpoi 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말