문제 링크

문제 해설

Idea

  • Backtracking
  • 0번째 계란부터 마지막 계란까지의 모든 경우의 수를 탐색
  • 시간 단축을 위해 현재 계란이 깨진 경우 또는 나머지 모든 계란이 깨진 경우를 예외로 처리
  • 한 번에 두 개 이상의 계란을 치는 경우를 방지하기 위해 계란을 친 후 원상복구 수행

Time Complexity

  • Backtracking: O(N^N) = 16,777,216

Data Size

  • N: 1 <= int <= 8
  • S, W: 1 <= int <= 300

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

N = int(input())
eggs = list()

for _ in range(N):
    eggs.append(list(map(int, input().split())))

answer = 0
def dfs(eggs, idx):
    global answer
    if idx == N:
        answer = max(answer, len([s for s,w in eggs if s < 1]))
        return

    if eggs[idx][0] < 1:
        dfs(eggs, idx+1)
        return

    if len([s for s,w in eggs if s < 1]) >= N-1:
        answer = max(answer, N-1)
        return

    for target in range(N):
        if target != idx and eggs[target][0] > 0:
            eggs[target][0] -= eggs[idx][1]
            eggs[idx][0] -= eggs[target][1]
            dfs(eggs, idx+1)
            eggs[target][0] += eggs[idx][1]
            eggs[idx][0] += eggs[target][1]

dfs(eggs, 0)
print(answer)