문제

백준 16987번: 계란으로 계란치기
https://www.acmicpc.net/problem/16987

풀이💡

알고리즘 분류

이 문제는 브루트포스, 백트래킹 알고리즘 문제입니다.
알고리즘 그대로 모든 가능한 경우를 확인하며, 종료조건을 만나면 return 해줍니다.

문제 풀 때 주의사항❗️

1. 재귀로 구현할 때는 항상 종료조건을 명시해야합니다.
2. 손에 든 계란을 제외한 모든 계란이 깨져있는 경우에도 반드시!!! 깨진 계란의 수를 확인하고 넘어가야합니다. 해당 경우가 최대일 수도 있기 때문에 확인하지 않고 넘어간다면 틀렸습니다 가 나옵니다.

   answer = max(answer, n - 1)

코드💛

import sys
input = sys.stdin.readline


def dfs(index, broken_cnt):
	# 종료 조건
    if index == n:
        global answer
        answer = max(answer, broken_cnt)
        return

    # 손에 든 계란이 깨졌다면, 다음 계란으로 넘어감
    if eggs[index][0] <= 0:
        dfs(index + 1, broken_cnt)
    else:
        all_broken = True
        for i, egg in enumerate(eggs):
            # 손에 든 계란이거나 이미 깨진 계란이면 넘어감
            if i == index or egg[0] <= 0:
                continue
            all_broken = False
            eggs[i][0] -= eggs[index][1]
            eggs[index][0] -= eggs[i][1]
            tmp = broken_cnt
            if eggs[i][0] <= 0:
                tmp += 1
            if eggs[index][0] <= 0:
                tmp += 1
            dfs(index + 1, tmp)
            eggs[i][0] += eggs[index][1]
            eggs[index][0] += eggs[i][1]

        # 손에 든 계란을 제외한 모든 계란이 깨져있는 경우
        if all_broken:
            answer = max(answer, n - 1)


n = int(input())
eggs = [list(map(int, input().split())) for _ in range(n)]
answer = 0
if n == 1:
    print(0)
else:
    dfs(0, 0)
    print(answer)