[백준/Python]16987: 계란으로 계란치기

문제

https://www.acmicpc.net/problem/16987
백준 문제집 - 0x0C강 - 백트래킹

 

알고리즘: 백트래킹, 브루트포스

---

풀이

계란을 치는 과정을 설명하면 아래와 같다.

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

이 과정을 통해 최대한 많은 계란을 깨는 것이 앞으로 인범이가 매일 아침마다 풀게 될 퍼즐이다. 그리고 유현이는 인범이가 찾은 답이 정답이 맞는지 확인해주려고 한다. 일렬로 놓인 계란들의 내구도와 무게가 차례대로 주어졌을 때 최대 몇 개의 계란을 깰 수 있는지 알아맞춰보자.

 

몇번째 계란을 깨는지와는 상관없이 집는 순서는 무조건 0 ~ N-1 순이다.

 

현재 계란의 번호를 curr 이라 했을때, 함수 실행 과정은 다음과 같다.

curr과 N이 같다면 모든 계란을 깼다는 소리이므로 결과값을 업데이트한다.
또는 curr번째 계란이 현재 깨져있는 상태라면 curr + 1번째 계란으로 재귀한다.

 

아니라면 0 ~ N-1 번째 계란 중 깨져있지 않은 계란을 내려친다.
내려친 후 curr 번째 계란과 내려친계란이 깨져있는지 체크하고 깨져있다면 카운트한다.
그리고 curr + 1번째 계란으로 재귀를 실행한다.

만약 모든 계란을 내려치지 않고 지나쳤다면 계란이 다 깨져있다는 소리이므로 curr + 1번째 계란으로 재귀를 실행하면 된다.

 

전체 코드

# 내구도, 무게를 따로 저장했을때
# 메모리: 31120KB / 시간: 2780ms
from sys import stdin


input = stdin.readline

N = int(input())
weight = []  # 무게
hard = []  # 내구도

for _ in range(N):
    h, w = map(int, input().split())
    hard.append(h)
    weight.append(w)

ret = 0

def breaking(hard, weight, curr, total_broken):
    global ret

    if curr == N:
        ret = max(ret, total_broken)
        return

    if hard[curr] <= 0:
        breaking(hard, weight, curr+1, total_broken)
        return

    no_break = True

    for target in range(N):
        if target != curr and hard[target] > 0:
            no_break = False

            hard[target] -= weight[curr]
            hard[curr] -= weight[target]

            broken = total_broken
            if hard[curr] <= 0:
                broken += 1
            if hard[target] <= 0:
                broken += 1

            breaking(hard, weight, curr+1, broken)

            hard[target] += weight[curr]
            hard[curr] += weight[target]

    if no_break:
        breaking(hard, weight, curr+1, total_broken)

breaking(hard, weight, 0, 0)
print(ret)

 

내구도와 무게를 한꺼번에 저장하는 방식보다 따로 관리하는게 더 빨랐다.

(큰 차이는 아니었음. 3168ms, 2780ms)