16987: 계란으로 계란치기

문제 링크

16987: 계란으로 계란치기

구현 방식

• 계란을 치는 과정을 보면, 백트래킹 문제임을 알 수 있다
  1. 가장 왼쪽의 계란을 든다.
  2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
  3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란 치는 과정을 종료한다.
• dfs의 idx는 현재 손에 들고 있는 계란의 index이다
  • 만약 idx가 N이 된다면 가장 오른쪽에 위치한 계란까지 모두 들었던 경우이므로, 깨진 계란의 최대값을 갱신해준다
  • 만약 현재 들고 있는 계란의 내구도가 음수라면 한칸 오른쪽의 계란을 든다 (dfs(idx+1) 호출)
  • flag 변수를 이용해서 가장 오른쪽에 도달하지 못하고 깰 계란이 없는 경우, answer는 갱신해줘야하기 때문에 dfs(N)을 호출해주었다

코드

import sys
input = sys.stdin.readline

N = int(input()[:-1])
eggs = [] #[내구도, 무게]
for n in range(N): eggs.append(list(map(int, input()[:-1].split())))

def dfs(idx):
    global answer
    if idx == N:
        cnt = 0
        for i in range(N):
            if eggs[i][0] <= 0: cnt += 1
        answer = max(answer, cnt)
        return

    if eggs[idx][0] <= 0: dfs(idx+1)
    else:
        flag = False
        for i in range(N):
            if i == idx: continue
            if eggs[i][0] <= 0: continue
            eggs[idx][0] -= eggs[i][1]; eggs[i][0] -= eggs[idx][1]
            dfs(idx+1); flag = True
            eggs[idx][0] += eggs[i][1]; eggs[i][0] += eggs[idx][1]
        if not flag: dfs(N) #가장 오른쪽에 도달하지 못하고 깰 계란이 없는 경우

answer = 0
dfs(0)
print(answer)