Python으로 백준 16987번을 풀어보자

 

오늘은 c++ 대신 파이썬으로 16987번 계란으로 계란치기 문제를 풀어보았다.

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

16987번: 계란으로 계란치기

문제가 제법 길어서 풀기 조금 싫었지만 크게 어려운 문제는 아니였다. (실버1)

 

 

• 풀이 설명
  • 1. 가장 왼쪽의 계란을 든다.
    2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
    3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
  • 긴 지문 중 이게 핵심이다. 이 과정을 재귀함수로 구현하면 된다.
  • 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 깨진 계란 수를 세고 함수를 종료하도록 한다.

 

• 코드 구현
  • 그런데 파이썬에서 리스트 = 리스트 하면 리스트가 복사되는게 아니라 참조가 되는 걸 망각하고 한참을 헤매었다 ... 그래서 한 쪽에서 변경하면 다른 쪽도 같이 변경되는 문제가 있었다.
    • 따라서 슬라이싱을 [:] 이용해 리스트 복사를 처리했다.
    • 아래의 링크 내용을 블로그에 정리해봐야할 것 같다. 
    • https://wikidocs.net/16038

n = int(input())
s = [0]*n
w = [0]*n

for i in range(n):
    s[i], w[i] = map(int, input().split())

res = 0 
def solve(idx, eggs):
    global res
    if idx == n:
        cnt = 0
        for i in range(n):
            if eggs[i] <= 0:
                cnt +=1
        if cnt > res:
            res = cnt
        return

    if eggs[idx] > 0:
        for i in range(n):
            flag = False
            if eggs[i] > 0 and i != idx:
                flag = True
                tmp = eggs[:]
                tmp[i] -= w[idx]
                tmp[idx] -= w[i]
                solve(idx+1, tmp)
        if not flag:
            solve(idx+1, eggs)
    else:
        solve(idx+1, eggs)

solve(0, s)
print(res)