[python] 백준 16987 계란으로 계란치기

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

16987번: 계란으로 계란치기

 

문제 해결

• 전형적인 백트래킹 문제
• 하나씩 차례로 부딪힐 수 있는 것을 부딪히고 다음 것을 부딪히고 하다가 끝까지 간후 다시 부딪히기 전으로 합치고 다음 것부터 부딪히고 모든 경우의 수를 계산해야한다.

 

CODE

n = int(input())
S = []
for _ in range(n):
    a, b = map(int, input().split())
    S.append([a,b])

def dfs(now):
    if now == len(S):
        cnt = 0
        for s, _ in S:
            if s<=0:
                cnt += 1
        return cnt
    
    if S[now][0] <=0:
        return dfs(now+1)
    for i in range(len(S)): # now와 깰 부딪힐 것이 잇는지 찾기
        if i == now: continue
        if S[i][0] >0: break
    else:
        return dfs(now+1) # 다른 것 찾기
    answer = 0
    for i in range(len(S)):
        if i == now: continue
        if S[i][0] <=0: continue

        S[i][0] -= S[now][1]
        S[now][0] -= S[i][1]

        answer = max(answer, dfs(now+1))

        S[i][0] += S[now][1]
        S[now][0] += S[i][1]

    return answer

print(dfs(0))