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

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

16987번: 계란으로 계란치기

 

 

1. 해결방법

문제를 이해하면 백트레킹이라는 것을 알 수 있지만, 이해도 어렵고 문장도 길어서 어떤 알고리즘인지 찾아내기가 꽤 어려웠다.

문제 이해하는데만 20~30분 정도는 걸린 것 같다.

https://burningjeong.tistory.com/536

이 문제에 대한 접근은 왼쪽부터 계란을 집어서 다른 계란을 때리는 것이다.

이 때, 내구도와 무게에 따라 들고있는 계란이 깨지는지 다른 계란이 깨지는지의 경우를 고려해야한다.

조건을 생각해 보면,
1. 들고 있는 계란이 깨진 경우,

2. 들고있는 계란을 제외한 모든 계란이 깨진 경우,

위 두 조건을 재귀를 돌때마다 체크를 해주어야 한다.

그리고 이 문제는 방문 체크를 권장하지 않는다. 그 이유는 들고 있는 계란이 모든 계란을 때려봐야 하기 때문에 인덱스를 기준으로 유효성 검사를 해주는 것이 좋다.

 

 

2. 정답코드

import sys
from collections import deque

input = sys.stdin.readline


N = int(input())

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

chk = [False] * N


def dfs(idx):
    global answer

    # 종료 지점
    if idx == N:
        count = 0
        for i in range(N):
            if eggs[i][0] <= 0:
                count += 1
        answer = max(answer, count)

        return

    # 들고 있는 계란이 깨진 경우,
    if eggs[idx][0] <= 0:
        dfs(idx + 1)
        return

    # 들고있는 계한 제외하고 나머지 계란이 다 깨져있는 경우,
    for i in range(N):
        if i != idx:
            if eggs[i][0] > 0:
                break
    else:
        answer = max(answer, N - 1)
        return

    # 떄리기
    for i in range(N):
        if i != idx and eggs[i][0] > 0:
            eggs[idx][0] -= eggs[i][1]
            eggs[i][0] -= eggs[idx][1]
            dfs(idx + 1)
            eggs[idx][0] += eggs[i][1]
            eggs[i][0] += eggs[idx][1]


answer = 0
dfs(0)
print(answer)

 

 

 

 

 

 

 

[참고]

https://kjhoon0330.tistory.com/entry/BOJ-16987-%EA%B3%84%EB%9E%80%EC%9C%BC%EB%A1%9C-%EA%B3%84%EB%9E%80%EC%B9%98%EA%B8%B0-Python