16987_계란으로 계란치기

입력

첫 번째 줄에 계란의 개수를 입력
N+1번째 줄까지 각 계란의 내구도 / 무게를 입력

출력

깰 수 있는 계란의 최대 개수

조건

• 왼쪽에는 깨지지 않은 계란 중 가장 왼쪽의 계란을 선택
• 오른쪽에는 깨지지 않은 계란 어떤 것이든 선택 가능
• 행동을 한 후 왼쪽에는 가장 최근에 든 계란의 1칸 옆에 있는 계란을 선택(만약 무게가 0일 경우 1칸 옆에 있는 계란을 선택)
• 왼쪽에 든 계란이 가장 오른쪽에 위치한 계란이면 stop

풀이

모든 경우의 수를 돌며 최대값을 구하는 문제이므로 dfs를 활용

1. 계란을 입력받음 (eggs[idx][0]=>내구도 / eggs[idx][1]=>무게)

2. 모든 경우의 수를 돌며 선택한 오른쪽 계란의 내구도가 0일 경우 다음 계란으로 넘어감
   그렇지 않을 경우 내구도를 계산하고 다음 오른쪽 계란으로 넘어감

   모든 계란의 내구도가 0일 경우 왼쪽 계란의 index 값을 N값으로 주어 stop

flag = False
    for right in range(N):
        if ans == N: return
        if eggs[right][0] <= 0 or right == idx: continue
        else:
            eggs[idx][0] -= eggs[right][1]
            eggs[right][0] -= eggs[idx][1]

            flag = True
            dfs(eggs, idx+1)

            eggs[idx][0] += eggs[right][1]
            eggs[right][0] += eggs[idx][1]

    if not flag: dfs(eggs, N)

3. 왼쪽 계란의 index값이 N일 경우 모든 계란을 확인하며 내구도가 0 이하인 것을 count

if idx == N:
    broken = 0
    for i in range(N):
        if eggs[i][0] <= 0: broken += 1
    ans = max(ans, broken)
    return
elif eggs[idx][0] <= 0:
    dfs(eggs, idx+1)
    return

전체 코드

계란으로 계란치기