[백준/파이썬] #16987

백트래킹으로 접근했는데, 테스트 케이스를 통과하진 못했다. 

def revert(hand, target):
    S[hand] += W[target]
    S[target] += W[hand]

def crack(hand, target):
    S[hand] -= W[target]
    S[target] -= W[hand]

def check_cracked_number():
    count = 0
    for s in S:
        if s <= 0:
            count += 1
    return count

def is_all_cracked():
    for s in S:
        if s > 0:
            return False
    return True

def solution(hand, target, total):
    print(hand, target, total)
    global answer
    new_total = total
    
    # 2번 과정
    if S[hand] > 0 and not is_all_cracked():
        crack(hand, target)
        
        if S[hand] <= 0:
            new_total += 1
        if S[target] <= 0:
            new_total += 1

    # 3번 과정
    if hand >= N-1:
        answer = max(check_cracked_number(), answer)
    else:
        if S[hand+1] > 0:
            for t in range(hand+1, hand+N):
                if t != hand+1 and S[t % N] > 0:
                    solution(hand+1, t % N, new_total)

    revert(hand, target)

if __name__ == "__main__":
    N = int(input())
    S = [0] * N     # 내구도
    W = [0] * N     # 무게

    for i in range(N):
        S[i], W[i] = map(int, input().split())

    answer = 0
    for t in range(1, N):
        solution(0, t, 0)
        revert(0, t)

    print(answer)

 

다른 풀이를 참고해봤다. 

def check(eggs):
    cnt = 0
    for e in eggs:
        if e[0] <= 0:
            cnt += 1
    return cnt


def solution(depth, arr):
    global answer
    if depth == n:
        answer = max(answer, check(arr))
        return
    # 현재 들고있는 계란이 깨졌을때
    if arr[depth][0] <= 0:
        solution(depth + 1, arr)
    else:
        isBroken = True
        for i in range(n):
            if depth != i and arr[i][0] > 0:
                isBroken = False
                arr[depth][0] -= arr[i][1]
                arr[i][0] -= arr[depth][1]
                solution(depth + 1, arr)
                arr[depth][0] += arr[i][1]
                arr[i][0] += arr[depth][1]
        if isBroken:
            solution(n, arr)


n = int(input())
egg = [list(map(int, input().split())) for _ in range(n)]
answer = 0
solution(0, egg)
print(answer)