글 읽기 - TC는 모두 통과하는데 특별히 코드에서 문제점을 찾지 못하겠습니다.

papayetoo 4년 전 0

치킨집 위치 와 각 집의 위치를 [tuple(y, x)] 식으로 저장해서 치킨 거리를 계산하는데

조합은 itertools combinations를 활용햇습니다.

어디서 틀린지 모르겠습니다.

from itertools import combinations
def chickenDistance(chkzip, homes):
    ret = 0
    for h in homes:
        # print('home :', h[0] +1, h[1] +1)
        temp = 10**3
        for chk in chkzip:
            # print('chicken zip :', chk[0] +1, chk[1] +1)
            dist = abs(chk[0]-h[0]) + abs(chk[1]-h[1])
            temp = min(temp, dist)
        # print('chicken distance: {}'.format(temp))
        ret += temp
    return ret


n, number = map(int, input().split())
arr = [list( map( int, input().split() ) ) for _ in range(n)]
chickenzip = []
home = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 2:
            chickenzip.append((i, j))
        if arr[i][j] == 1:
            home.append((i, j))
ans = 10**3
lst =  [i for i in range(len(chickenzip))]
comb = []
for i in range(1, number+1):
    tmp = list(combinations(chickenzip, i))
    comb += tmp
# print(comb)
for data in comb:
    dist = chickenDistance(data, home)
    ans = min(ans, dist)
print(ans)

shg9411 4년 전 1

일단 29번째 줄에서 폐업하지 않을 지점은 정확히 number개만큼 i를 설정하셔야 하는 것 아닌가싶네요.

shg9411 4년 전 1

위 댓글은 불필요한 부분이 있어서 남긴거고 (현재 가장 큰 케이스에서는 시간이 4배 소요됩니다.)

도시는 최대 100개가 있을 수 있기에 10**3이라는 Max로 잡아놓으신 값이 문제가 됩니다.

papayetoo 4년 전 0

Max 값을 변경하니 문제 해결했습니다.

가장 큰 케이스에서 시간이 오래 걸리는 것은 개선하기 위해서 다른 조합 방법을 이용해서 풀어보겠습니다.

댓글 감사합니다 :)👍

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

문제

문제

출처

ICPC

TC는 모두 통과하는데 특별히 코드에서 문제점을 찾지 못하겠습니다.

papayetoo 4년 전 0

shg9411 4년 전 1

shg9411 4년 전 1

papayetoo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말