[SWEA] 2383. 점심 식사시간(python)

계단마다 사람을 배치하는 것은 모든 경우의 수를 다 고려했다.

계단과 사람과의 거리를 나타내는 배열 order, 계단입구를 나타내는 배열 entry, 계단을 내려가는 횟수를 기록하는 배열 down을 만들어 구현하였다.

예시

from itertools import combinations
T = int(input())
def downTo(people,stair):
    order,down,entry=[],[],[]
    stairSize=stair[2]
    for person in people:
        order.append(abs(stair[0]-person[0])+abs(stair[1]-person[1]))
    order.sort()
    time=0
    while order:
        time+=1
        while entry and len(down)<3:
            down.append(entry.pop(0))
        for i in range(len(down)):
            down[i]-=1
        while 0 in down:
            down.remove(0)
        while order and order[0]<=time:
            order.pop(0)
            entry.append(stairSize+1)
    while down or entry:
        time+=1
        for i in range(len(down)):
            down[i]-=1
        while 0 in down:
            down.remove(0)
        while entry and len(down)<3:
            down.append(entry.pop(0))
    return time-1

for tc in range(1, T + 1):
    N=int(input())
    maps=[list(map(int,input().split())) for _ in range(N)]
    people=set()
    stair=[]
    result=9999
    for row in range(N):
        for col in range(N):
            if maps[row][col]==1:
                people.add((row,col))
            elif maps[row][col]>1:
                stair.append((row,col,maps[row][col]))
    for i in range(len(people)+1):
        choice=set(combinations(people,i))
        for c in choice:
            maxNum=max(downTo(set(c),stair[0]),downTo(people-set(c),stair[1]))
            result=min(result,maxNum)
    print(f'#{tc} {result}')

 

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl 

SW Expert Academy