[BOJ] 16987. 계란으로 계란치기 (🥇, 백트래킹)

🔗

풀이

1. 가장 왼쪽 계란부터 순차적으로 시작한다
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중 하나를 친다.
3. 손에 들고 있는 계란이 깨졌거나 or 더 이상 깰 계란이 없으면 넘어간다.
4. 방금까지 손에 들고 있던 계란 바로 오른쪽에 있는 계란으로 과정을 반복한다.

여기서 핵심은 깨지지 않은 다른 계란 중 한 개만 쳐야 한다는 거다.
이걸 놓쳐서 한 번 계란을 집으면 나머지 한 번씩 다 쳐보거나 그 계란이 깨질때까지 쳐야 되는 줄 알았다.

import sys
input = sys.stdin.readline

def is_left(now, dura):
    for i in range(n):
        if i != now and dura[i] > 0:
            return True
    return False

def dfs(now):
    global answer
    if now == n:
        answer = max(answer, sum(1 for i in range(n) if dura[i] <= 0))
        return 
    
    if dura[now] <= 0:
        dfs(now+1)
        return 

    if not is_left(now, dura):
        dfs(now+1)
        return 
    
    for i in range(n):
        if i == now or dura[i]<=0:
            continue
        dura[i] -= weight[now]
        dura[now] -= weight[i]
        dfs(now+1)
        dura[i] += weight[now]
        dura[now] += weight[i]

n = int(input())
dura, weight = list(map(list, zip(*[map(int, (input().split())) for _ in range(n)])))

answer = 0
dfs(0)
print(answer)