[BOJ] 16987 계란으로 계란치기 - Python

🤔 문제

---

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

 

😀 풀이

---

위 문제는 주어진 N값과 시간 제한, 문제 상황을 고려해보았을 때 완전탐색이 가능합니다. 상황 종료 조건이 명확하고 비슷한 행동을 반복적으로 수행하므로 재귀 함수를 이용하여 문제를 풀어보았습니다.

재귀 함수( crash )에 대한 설명은 아래와 같습니다.

1. crash 함수의 nowIndex 인자는 현재 들고 있는 계란의 인덱스 입니다.

2. 가장 오른쪽 계란을 치고 난 뒤가 종료 조건이므로 nowIndex가 n 이 되는 순간이 종료 시점이고 이때 부서진 계란의 개수를 세 정답을 갱신합니다.

3. 현재 들고 있는 계란이 깨져 있는 경우 crash( nowIndex + 1 )을 호출하여 다음 계란으로 넘어갑니다.

4. 현재 들고 있는 계란 외에 다 깨져 있는 경우 칠 계란이 더 이상 없으므로 정답을 갱신하고 함수를 끝냅니다.

5. 칠 계란이 있는 경우 칠 수 있는 모든 경우에 대해 재귀함수를 진행시켜 계란들을 쳐보고 원본 배열을 복구시킵니다.

 

💻 풀이 코드는 아래와 같습니다.

n = int(input())
eggs = []
answer = 0
S, W = 0, 1

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

def crash(nowIndex):
    global answer
    # 종료조건
    if nowIndex == n:
        breakEggs = 0
        for i in range(n):
            if eggs[i][S] <= 0:
                breakEggs += 1
        answer = max(answer, breakEggs)
        return

    # 자기가 깨져있는 경우 다음 계란으로
    if eggs[nowIndex][S] <= 0:
        crash(nowIndex + 1)
        return
    
    # 자기말고 다 깨져있는 상황인 경우
    isAllBroken = True
    for targetIndex in range(n):
        if targetIndex == nowIndex: continue
        if eggs[targetIndex][S] > 0:
            isAllBroken = False
            break
    if isAllBroken:
        answer = max(answer, n - 1)
        return

    # 때려보기
    for targetIndex in range(n):
        if targetIndex == nowIndex: continue
        if eggs[targetIndex][S] <= 0: continue
        # 때리기
        eggs[nowIndex][S] -= eggs[targetIndex][W]
        eggs[targetIndex][S] -= eggs[nowIndex][W]
        crash(nowIndex + 1)
        # 복구
        eggs[nowIndex][S] += eggs[targetIndex][W]
        eggs[targetIndex][S] += eggs[nowIndex][W]
        
crash(0)
print(answer)