[BaekJoon] "백트래킹" - 백준 16987번 문제 : 계란으로 계란치기

[문제 설명]

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

16987번: 계란으로 계란치기

 

각 계란에는 내구도와 무게가 정해져 있음

계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎이게 됨

내구도가 0 이하가 되는 순간 계란은 깨지게 됨

계란을 치는 과정은 아래와 같음

1. 가장 왼쪽의 계란을 듦

2. 손에 들고 있는 계란은 깨지지 않은 다른 계란 중에서 하나를 침

단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어감

이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행

3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행

단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정 종료

최대 몇 개의 계란을 깰 수 있는지 출력

 

[해결 로직]

- 사실 이해가 너무 안돼서,, 다른 블로그 참고해서 풀었다 ㅠ

- 이해한 대로 이야기 해보자면,

- 만약 현재 들고 있는 계란이 맨 오른쪽 계단일 때, 이때까지 깨져있는 계란의 수를 체크해서 카운팅

- 만약 현재 든 계란이 깨졌다면, 다음 오른쪽 계란으로 수행

- 만약 다 깨져 있는 경우에는 자기 빼고 전부 다니깐, 현재 저장된 최대로 깰수 있는 계란수와 비교해서 맥스 값 도출

- 현재 든 계란을 기준으로 옆에 계란을 하나씩 집어서 깨는데 내구도를 깎았다가, 만약 특정 조건에 성립해서 재귀를 탈출하면 이전에 뺀 내구도를 다시 원상 복구 해줘야함

- 세부 사항은 블로그 참고..

 

[Solution 코드]

n = int(input())

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


def eggdfs(idx):
    global rslt

    ## 만약 끝까지 왔다면? 현재까지 깨진 계란 수 저장하고 탈출

    if idx == n:
        total = 0
        for i in range(n):
            if ary[i][0] <= 0 : ## 내구도가 0 이하면 깨진 거임
                total += 1 ### 깨진 계란 수 저장
    
        rslt = max(rslt, total) ## 깰수 있는 계란의 최대 개수
        return
    
    if ary[idx][0] <= 0 :  ## 현재 들고 있는 계란이 깨졌다면?
        eggdfs(idx + 1) ## 다음꺼로 넘겨줌 계란을
        return
    
    check = True # 현재 계란이 다 꺼져있는지 확인하기 위한 것 (자기 빼고)
    for i in range(n):
        if i == idx:## 자기 빼고
            continue
        if ary[i][0] > 0:
            check = False
            break
        else:
            check = True


    if check: ## 다 깨져있는 경우  #자기빼고 전부다니깐 N-1
        rslt = max(rslt, n-1)

    for i in range(n):
        if i == idx or ary[i][0] <=0: 
            continue
        ary[idx][0] -= ary[i][1]
        ary[i][0] -= ary[idx][1]

        eggdfs(idx + 1)

        ary[idx][0] += ary[i][1]
        ary[i][0] += ary[idx][1]



rslt = 0
eggdfs(0)

print(rslt)

 

Ref :

https://velog.io/@030831/%EB%B0%B1%EC%A4%80-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

백준 16987 : 계란으로 계란치기 (Python)

https://howudong.tistory.com/251

[C++] 백준/BOJ - 16987 : 계란으로 계란치기

 

어렵다 어려워....