BOJ 16987: 계란으로 계란치기 [Python 3]

이 문제는 dfs와 유사한 방법 (백트래킹)으로 풀 수 있다.

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

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

16987번: 계란으로 계란치기

---

풀이

 

n=int(input())
data=[]
for i in range(n):
    data.append(list(map(int,input().split())))
res=0
def solve(idx,data):
    global res
    if idx==n:
        cnt=0
        for i in range(n):
            if data[i][0]<=0:
                cnt+=1
        res=max(res,cnt)
        return
    if data[idx][0]<=0:
        solve(idx+1,data)
    else:
        for i in range(n):
            allBroken=True
            if idx!=i and data[i][0]>0:
                allBroken=False
                data[idx][0]-=data[i][1]
                data[i][0]-=data[idx][1]
                solve(idx+1,data)
                data[idx][0]+=data[i][1]
                data[i][0]+=data[idx][1]
        if allBroken:
            solve(n,data)
solve(0,data)
print(res)

data라는 함수에 계란의 내구도와 무게를 저장하고,

아래쪽 for문에서,

계란의 index가 자기 자신이 아니고, 그 계란이 깨진 계란이 아니라면, 둘을 부딪히는 식으로 하여서,

dfs로 이어가서 문제를 해결했습니다.

 

여담이지만, data라는 리스트는 함수 밖에서 global하게 선언된 리스트이기 때문에

solve(idx+1,data) 전에

tmp==data[:] 식으로 temporary list를 만들어서,

tmp 내에서 계란을 서로 깨면 

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

해당 내용을 추가할 필요가 없어진다.

(물론 memory는 더 사용해야겠지만...)