BAEKJOON 14502チキン出前

質問する

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

に答える

1からMから構成することができるフライドチキンの店について、全部の数量の

を求めます

この場合の数は、フライドチキン店とファミリーショップの距離を得るごとに、最高価格

に更新される.

コード#コード#

import sys
sys.stdin = open('input.txt')

def get_combi(arr,start,n,temp):                    # 치킨집의 경우의 수를 구하는 함수
    if len(temp) == n:
        get_dist(home_idx,temp)

    for i in range(start,len(arr)):
        if visit[i] == 0:
            visit[i] = 1
            get_combi(arr, i, n, temp+[arr[i]])
            visit[i] = 0

def get_dist(home, chicken):                        # 치킨집과 가정집 사이의 최단 거리를 구하는 함수
    global cnt
    result = 0
    for i in home:
        mmin = 1000
        for j in chicken:
            dist = abs(j[0]-i[0])+abs(j[1]-i[1])
            if dist < mmin:
                mmin = dist
        result += mmin
    if result < cnt:
        cnt = result

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

home_idx = []
chicken = []
for i in range(len(arr)):                                   # 미리 치킨집과 가정집의 idx를 구함
    for j in range(len(arr)):
        if arr[i][j] == 1:
            home_idx.append([i+1,j+1])
        if arr[i][j] == 2:
            chicken.append([i+1,j+1])



visit = [0]*(len(chicken)+1)

cnt = 1000000
for i in range(1,M+1):                                      # 치킨집의 idx를 가능한 수에 대해 가능한 경우의 수를 모두 구해서 가정집과의 거리를 비교함
    chicken_good = []
    get_combi(chicken, 0,i,[])

print(cnt)

結果

組み合わせを利用すれば解決しやすい問題です.実施も難しくないと思いますので、簡単に解決できました.すべての状況を考慮するだけで、時間は少し残念なようです.どうすればいいか考えて追跡すればいい