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

브루트포스, 백트래킹 / 골드 5

🥚

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

16987번: 계란으로 계란치기

 

 

내 풀이

def dfs(n):
    ans = 0

    if n == N: # 모든 계란을 검사한 경우 종료
        cnt = 0
        for i in range(N):
            if eggs[i][0] <= 0:
                cnt += 1
        return cnt
    
    if eggs[n][0] <= 0: # 현재 계란이 깨진 경우
        return dfs(n+1) # 다음 계란으로 이동
    
    # 껠 수 있는 계란이 있는지 검사
    egg = 0 
    for j in range(N):
        if n == j:
            continue
        if eggs[j][0] > 0:
            egg += 1
            break

    if egg == 0: # 깰 수 있는 계란이 없는 경우 다음 계란으로 이동
        return dfs(n+1)
    

    for k in range(N):
        if k != n and eggs[k][0] > 0: # 같은 계란이 아니면서 깰 수 있는 계란인 경우
            eggs[k][0] -= eggs[n][1]
            eggs[n][0] -= eggs[k][1]

            ans = max(ans, dfs(n+1))

            eggs[k][0] += eggs[n][1]
            eggs[n][0] += eggs[k][1]

    return ans


N = int(input())
eggs = []

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

print(dfs(0)) # 현재 계란의 위치

 

 

 

코드 설명

 

eggs: 계란의 내구도와 무게를 저장하는 이차원 리스트

 

dfs의 매개변수로는 현재 계란의 위치를 넘겨준다. 0에서 시작한다.

N = int(input())
eggs = []

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

print(dfs(0)) # 현재 계란의 위치

 

 

✔️ dfs 함수

 

ans: 깰 수 있는 계란의 최대 개수

ans = 0

 

모든 계란을 검사한 경우 깨진 계란의 수를 리턴하며 종료한다.

내구도가 0 이하라면, 깨진 계란이다.

if n == N: # 모든 계란을 검사한 경우 종료
    cnt = 0
    for i in range(N):
        if eggs[i][0] <= 0:
            cnt += 1
    return cnt

 

현재 계란이 깨진 경우, 칠 수 없으므로 다음 계란으로 이동한다.

if eggs[n][0] <= 0: # 현재 계란이 깨진 경우
    return dfs(n+1) # 다음 계란으로 이동

 

egg: 깰 수 있는 계란이 존재하는지 구분하는 변수 (0: 깰 수 있는 계란이 없음, 1: 깰 수 있는 계란이 있음)

# 껠 수 있는 계란이 있는지 검사
egg = 0 
for j in range(N):
    if n == j:
        continue
    if eggs[j][0] > 0:
        egg += 1
        break

 

깰 수 있는 계란이 없다면, 다음 계란으로 이동한다.

if egg == 0: # 깰 수 있는 계란이 없는 경우 다음 계란으로 이동
    return dfs(n+1)

 

계란을 치는 과정을 진행한다.

서로 다른 계란이면서, 내구도가 양수인 경우(깰 수 있는 계란인 경우) 서로의 내구도를 상대 계란의 무게만큼 감소시킨다.

dfs를 호출하여, ans를 최대 값으로 갱신한다.

내구도를 원상태로 복구한다.

for k in range(N):
    if k != n and eggs[k][0] > 0: # 같은 계란이 아니면서 깰 수 있는 계란인 경우
        eggs[k][0] -= eggs[n][1]
        eggs[n][0] -= eggs[k][1]

        ans = max(ans, dfs(n+1))

        eggs[k][0] += eggs[n][1]
        eggs[n][0] += eggs[k][1]

 

 

백트래킹이 아직 익숙하지 않아서 조금 어려웠당 🙀