파이썬에서 도둑이 금고를 털 수 있는지 확인하는 프로그램

N개의 강도가 금고를 털려고 한다고 가정합니다. 경비원이 있었지만 그는 얼마 동안 외출했다가 다시 돌아올 것입니다. 그리고 각 강도는 금고를 털기 위한 특정한 시간을 가지고 있지만, 그들 중 기껏해야 두 사람이 금고에 동시에 들어갈 수 있습니다. 이제 문제는 경비원에게 잡혀 금고를 털 수 있는지 확인해야 한다는 것입니다. 우리는 다음을 명심해야 합니다 -

• 한 강도가 시간 t에 금고에 들어갔다가 동시에 다른 강도가 나오면 금고에 동시에 들어가지 않은 것과 같습니다.

• 경비원이 G 시간에 금고 안으로 들어가고 정확히 G 시간에 강도가 나온다면 경비원은 도둑을 눈치채지 못할 것입니다.

따라서 입력이 N =3 G =5 time =[3,5,2]와 같으면 출력은 True가 됩니다. 가능한 배열이 있기 때문입니다. 즉 -

• 시간 t=0에 robber1이 안으로 들어갔다가 t=3에 나옵니다.
• 시간 t=0에 robber2가 들어가 t=5에 나옵니다.
• 시간 t=3에 robber3이 안으로 들어갔다가 t=5에 나옵니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 시간의 모든 요소의 합> 2*G이면
  • 거짓을 반환
• 그렇지 않으면 시간의 모든 요소의 합이 <=G일 때
  • 참 반환
• 그렇지 않으면
  • valid :=크기가 G + 1인 배열이며 처음에는 모든 값이 False입니다.
  • 유효한[0] :=참
  • 각 x에 대해 다음을 수행합니다.
    • G ~ 0 범위의 i에 대해 1 감소, do
      • i-x>=0이고 유효한[i-x]이면
        • 유효한[i] :=참
  • 시간에 있는 모든 요소의 합 - 유효할 때 범위 0에서 유효한 크기까지 모든 i에 대한 i의 최대값[i] <=G이면
    • 참 반환
  • 그렇지 않으면
    • 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(N, G, time):if sum(time)> 2*G:False 반환 elif sum(time) <=G:반환 True else:유효 =[False]*(G+1) 유효 [0] =시간 내 x에 대해 참:범위 내 i에 대해(G,-1,-1):i-x>=0이고 유효한 경우[i-x]:유효[i] =합(시간) - 최대(i for i in range(len(valid)) if valid[i] <=G:반환 True else:return FalseN =3G =5time =[3,5,2]print(solve(N, G, time)) 
입력
 
3,5,[3,5,2]
 
출력
 
사실