[백준] 16987번: 계란으로 계란치기 파이썬

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

계란치기문제!

문제에 서론이 좀 긴데 다 무시하고

요악하자면

 

계란들끼리 서로 부딪쳐서 최대한 많은 계란을 깨는 문제. 각 계란에는 내구도와 무게가 있다. 계란을 부딪치면 내구도가 상대 계란의 무게만큼 감소하고, 내구도가 0 이하가 되면 계란이 깨진다.

1. N개의 계란이 일렬로 놓여있다.
2. 왼쪽부터 차례로 계란을 들어 다른 계란을 친다.
3. 계란이 깨지면 더 이상 칠 수 없다.
4. 최대 몇 개의 계란을 깰 수 있는지 구한다.

입력:

• 첫 줄에 계란의 수 N (1 ≤ N ≤ 8)
• 다음 N개의 줄에 각 계란의 내구도와 무게가 주어진다.

출력:

• 깨진 계란의 최대 개수를 출력.

(고마워 gpt)

 

풀이

import sys

# h = 손에든 계란 번호
def egg(h):
  global mx, count
  if h == n:
    mx = max(mx, count)
    return 
  if s_arr[h] <= 0 or count == n-1:
    egg(h+1)
    return
  for i in range(n):
    if s_arr[i]>0 and h != i:
      s_arr[i] -= w_arr[h]
      s_arr[h] -= w_arr[i]
      if s_arr[i] <= 0:
        count += 1
      if s_arr[h] <= 0:
        count += 1
      egg(h+1)
      if s_arr[i] <= 0:
        count -= 1
      if s_arr[h] <= 0:
        count -= 1
      s_arr[i] += w_arr[h]
      s_arr[h] += w_arr[i]

n = int(sys.stdin.readline())
s_arr = []
w_arr = []
count =0
mx = 0
for i in range(n):
  s, w = map(int, sys.stdin.readline().split())
  s_arr.append(s)
  w_arr.append(w)
egg(0)
print(mx)