백준 16987 계란으로 계란치기 Python

🐸 문제 정보

16987번: 계란으로 계란치기

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

28.16m

 

📝 풀이

백트래킹으로 풀면 되는 문제였다.

새로운 배열을 복사해서 전달해주는 방식보다는, 기존 배열 하나에서 재귀 시킨 후 다시 원상 복구 해주는 방식으로 진행했다.

아래 조건만 잊지 않으면 어렵지 않게 풀 수 있는 문제였다.

• 계란을 첫 인덱스부터 탐색하지만, 이미 깨져있는 경우나 본인인 경우는 패스해주는 것
• 깰 계란이 없으면 그냥 넘겨줄 것
• 본인이 이미 깨져있으면 그냥 넘겨줄 것

 

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
eggs = [list(map(int, input().rstrip().split())) for _ in range(n)]
res = 0

def bt(idx):
    global res
    if idx == n:
        res = max(res, sum(1 for egg in eggs if egg[0] <= 0))
        return
    if eggs[idx][0] > 0:
        flag = False
        for i in range(n):
            if eggs[i][0] > 0 and i != idx:
                flag = True
                eggs[idx][0] -= eggs[i][1]
                eggs[i][0] -= eggs[idx][1]
                bt(idx + 1)
                eggs[idx][0] += eggs[i][1]
                eggs[i][0] += eggs[idx][1]
        if not flag:
            bt(idx + 1)
    else:
        bt(idx + 1)

bt(0)
print(res)