[ 16987 ] [ Recursion ] 계란으로 바위치기

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

16987번: 계란으로 계란치기

 

---

풀이 과정

---

1. 문제 이해하기가 제일 어려웠음. 즉, 계란을 왼쪽에서 오른쪽으로 한번씩 들어야 함. 또한 전체 계란 중에서 깨지지 않은 계란이 있다면 칠 수 있으며, 손에 든 계란이 깨졌거나 더이상 깨뜨릴 계란이 없다면 한 칸 오른쪽 계란을 들면 됨. 여기서 더이상 깨뜨릴 계란이 없다면, 계속 오른쪽으로 이동하여 결국 종료하게 될 것
2. 재귀함수를 구성한다.
   1. 현재 단계가 마지막 단계라면(맨 오른쪽 계란까지 모두 끝난 상태), 전체 계란을 조사하면서 계란이 몇개 깨졌는지 카운팅 해주어야 함.
   2. 현재 손에 든 계란이 깨져있거나 안깨진 계란이 없다면 바로 현재 계란의 다음 계란으로 이동함.
   3. (2)를 통과하게 된다면, 시뮬레이션 해주어야 함. 칠 수 있는 계란을 한번씩 다 쳐보는 과정. 하나의 계란을 쳐본 다음에는 다시 더해서 원래 계란으로 만들어 주고, 다음 계란을 쳐주어야 함.
3. 정답을 출력한다.

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline()

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

def solve(current):
    if current == len(eggs):
        count = 0
        for s, w in eggs:
            if s <= 0:
                count += 1
                
        return count
    # 현재 손에 든 계란 깨짐
    if eggs[current][0] <= 0:
        return solve(current+1)

    # 안깨진 계란이 남아있는지 체크하는 부분
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] > 0:
            break
    else:
        return solve(current+1)
            
    # 시뮬레이션
    answer = 0
    for i in range(len(eggs)):
        if i == current:
            continue
        if eggs[i][0] <= 0:
            continue

        eggs[i][0] -= eggs[current][1]
        eggs[current][0] -= eggs[i][1]
        
        answer = max(answer, solve(current+1))

        # 다음 차례 가려면 기존에 빼주었던거 다시 더해주어야 함.
        eggs[i][0] += eggs[current][1]
        eggs[current][0] += eggs[i][1]
    
    return answer

print(solve(0))