[백준 16987번] 계란으로 계란치기

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

import sys

input = sys.stdin.readline

# 각 계란에는 내구도와 무게가 정해져있다
# 계란으로 계란을 치게 되면 각 계란의 내구도는 '상대 계란의 무게'만큼 깎이게 된다

# 그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 된다

# 일렬로 놓여있는 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제

# 1. 가장 왼쪽의 계란을 든다.

# 2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.
# (단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.)

# 3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행
# (단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료)

# 일렬로 놓인 계란들의 내구도와 무게가 차례대로 주어졌을 때 최대 몇 개의 계란을 깰 수 있는지 알아맞춰보자.

n = int(input())

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

answer = float("-inf")

def dfs(index, count):
    
    global answer

    answer = max(answer,count)
    
    if index >= n:
        return
        
    if eggs[index][0] <= 0:
        dfs(index+1,count)

    else:
        for i in range(n):
            if i != index and eggs[i][0] > 0 and (count+(n-index)*2) > answer: # 백트래킹(가지치기)
                cr, cw = eggs[index][0], eggs[index][1]
                nr, nw = eggs[i][0], eggs[i][1]
                
                eggs[i][0] -= cw
                eggs[index][0] -= nw

                if eggs[i][0] <= 0 and eggs[index][0] <= 0:
                    dfs(index+1,count+2)
                elif eggs[i][0] <= 0 or eggs[index][0] <= 0:
                    dfs(index+1,count+1)
                else:
                    dfs(index+1,count)

                eggs[i][0] += cw
                eggs[index][0] += nw
                    
dfs(0,0)

print(answer)

 

이번 문제는 N개의 달걀에 (내구도, 무게)가 각각 주어지고, 계란이 부딪힐 때마다 상대 계란의 무게만큼 내구도가 떨어진다고 가정했을 때 하나씩 순서대로 계란을 쳤을 경우 최대로 깰 수 있는 달걀의 수를 구하는 문제이다.

 

먼저 이 문제를 보자마자 완전탐색으로 풀이해야겠다고 판단했고, 계란이 깨지는 개수에 따라 count를 다르게 DFS 알고리즘의 인자로 전달해주었다.(탐색을 한 이후에는 다른 경우에 영향을 주지 않기 위해 내구도를 복구시켜주었다.)

 

하지만 이 문제를 단순히 완전탐색으로만 풀게 되면 입력값이 커질 때 시간초과가 발생하게 된다.

 

따라서 앞으로 남은 계란들 모두 양측 2개가 깨진다고 해도 현재까지 구한 값보다 크지 않으면 탐색을 하지 않도록 가지치기(Pruning)하여 시간초과를 해결하였다.((count+(n-index)*2) > answer) 

 

완전탐색과 백트래킹을 연습해볼 수 있었던 좋은 문제였다 :)