[백준] 16987_계란으로 계란치기 (Python)

16987_계란으로 계란치기 (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 16987번: 계란으로 계란치기

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
8 5
1 100
3 5

- 예제 출력 1 -
3

- 예제 입력 2 -
3
1 100
8 5
3 5

- 예제 출력 2 -
2

- 예제 입력 3 -
1
123 45

- 예제 출력 3 -
0

- 예제 입력 4 -
8
222 117
176 92
287 6
284 81
221 96
263 96
188 40
225 1

- 예제 출력 4 -
4

- 예제 입력 5 -
6
65 281
272 145
233 175
229 12
99 88
142 159

- 예제 출력 5 -
6

(3) 코드

import sys

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

def dfs(index, eggs):
  global answer

  if index == n:
    # 마지막 계란 까지 집은 경우
    answer = max(answer, check(eggs))
    return

  if eggs[index][0] <= 0:
    # 현재 계란의 내구도가 다 달았을 때 다음 계란으로 넘어간다.
    dfs(index + 1, eggs)

  else:
    # 현재 계란의 내구도가 남아있을 때 다른 계란들과 부딪친다. (현재 계란 제외, 내구도가 없는 계란 제외)
    is_all_broken = True
    for i in range(len(eggs)):
      if index != i and eggs[i][0] > 0:
        is_all_broken = False
        eggs[index][0] -= eggs[i][-1]
        eggs[i][0] -= eggs[index][-1]
        dfs(index + 1, eggs)
        eggs[index][0] += eggs[i][-1]
        eggs[i][0] += eggs[index][-1]

    # 모든 계란이 깨져있는 경우 dfs를 바로 빠져나와준다.
    if is_all_broken:
      dfs(n, eggs)

n = int(input())
eggs = []
answer = 0
for _ in range(n):
  eggs.append(list(map(int, input().split())))

dfs(0, eggs)
print(answer)

(4) 정리

예제 입력1 과 예제 입력2 의 결과가 왜 같은지 이해가 안되서 엄청 헤맸다.
처음에 모든 경우의 수로 다 쳐본다고 생각하고 시작했던게 이유였다.

---

• 무조건 가장 왼쪽(처음)의 깨지지 않은 계란을 먼저 들고 계란 치는 행위를 시작한다.(이때 어느걸 먼저 치던지 상관없다.)
• 경우1) 들었던 계란이 깨진 경우 깨지지 않은 다음 계란을 들고 계란 치는 행위를 반복한다.
• 경우2) 들었던 계란으로 다른 계란을 쳤는데 다른 계란이 깨지지 않은 경우 다음 계란을 들고 계란치는 행위를 반복한다.
• 모든 계란이 깨진 경우 종료한다.
• 마지막 계란을 들었을 경우도 종료한다.

(5) 참고

참고 풀이
이해가 쉬운 풀이