사이트 #문제: 문제유형 / 난이도

문제 링크 :

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

Problem

• 입력 : 계란수 N / 계란 내구도 & 무게 - s ,w
• 출력: 깰 수 있는 최대 계란 수
• 계란 깨기 동작 조건 i.가장 왼쪽 계란을 선택 ii. 손 위 계란 깨짐 or 깨짐 -> 넘어감 => 손위 든 계란 윈위치 iii. 바로 선택한 계란 그 오른쪽 계란 선택 => 2번 재 진행

solution

• 유형 : Brute force + pruning
  • 계란 선택하는 모든 경우의 수 고려 그 중 최대값
  • 재귀 [1] backtracking 재귀 함수 상태 매개변수 선택한 계란idx, 생존 달걀의 idx의 리스트 , 현 내구도 및 무게 상태 [2] 종료 조건 (1) 선택 계란 다 선택 했을때 idx >= N 일때 (2) 남은 계란 다 깼을떄 => 부순 계란 최대값 반환 [3] 나머지 동작 과정
    • 선택 계란 i 외 안 꺠진 다른 계란들 선택하기
    • 서로 충돌시키고 남은 내구도 업데이트
    • if 내구도 <1 => 죽음
    • 다름 i+1 & 생존 계란 선택하기

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

🚩제출한 코드

"""
<https://www.acmicpc.net/problem/16987>
# Problem
- 입력 : 계란수 N / 계란 내구도 & 무게 - s ,w 
- 출력: 깰 수 있는 최대 계란 수
- 계란 깨기 동작 조건
  i.가장 왼쪽 계란을 선택 
  ii. 손 위 계란 깨짐 or 깨짐 -> 넘어감 => 손위 든 계란 윈위치
  iii. 바로 선택한 계란 그 오른쪽 계란 선택 => 2번 재 진행

# solution
- 유형 : Brute force + pruning
  - 계란 선택하는 모든 경우의 수 고려 그 중 최대값
  - 재귀
    [1] backtracking 재귀 함수 상태 매개변수 
      선택한 계란idx,  생존 달걀의 idx의 리스트 , 현 내구도 및 무게 상태 
    [2] 종료 조건 
      (1) 선택 계란 다 선택 했을때 idx >= N 일때
      (2) 남은 계란 다 깼을떄
      => 부순 계란 최대값 반환
    [3] 나머지 동작 과정
      - 선택 계란 i 외 안 꺠진 다른 계란들 선택하기
      - 서로 충돌시키고 남은 내구도 업데이트
      -   if 내구도 <1 => 죽음 
      - 다름 i+1 & 생존 계란 선택하기
pruning 
- 남은 횟수(N-n)에서 모두 깨도 최대값 업데이트 불가
  (N-n)*2
"""
import sys

#0. 입력 변수 정의 및 초기화 하기
input= sys.stdin.readline
N = int(input())
eggs = [[] for _ in range(N)]

for i in range(N):
  durability , weight =map(int ,input().split())
  eggs[i] = [durability , weight]

# 1. backtracking 수행하기
max_cnt = 0 
def backtracking(idx,cnt) :
  global max_cnt
  print(f"stage {idx}")
  # pruning 조건 : 현재 남은 횟수로 2개씩 깨도  max_cnt 업데이트 불가 경우
  if max_cnt >= (cnt + (N-idx)*2):
    
  #1. 종료 조건 : (1. 모든 계란 선택 완료 n == N)
  if idx >= N : # 1개 이하 남아있을떄 
    max_cnt = max(max_cnt , cnt)
    return 0 
  
  #1-2. 현재 선택한 계란 (idx) 가 깨져있는 경우
  if eggs[idx][0] <= 0 : 
    backtracking(idx+1 , cnt)
  #2.동작 과정- 계란 깨기
  else : # 현재 계란 lived -> 부딫힐 계란 선택 & 부딫치기
    flag =False
    for j in range(N) :#현재 계란 부딫칠 계란 선택 (본인idx 아님 or 생존 )
      if j!= idx and eggs[j][0] > 0 : 
        # 충돌
        eggs[idx] =eggs[idx] -eggs[j][1]
        eggs[j] =eggs[j] -eggs[idx][1]
        backtracking(idx+1 , cnt+int(eggs[idx][0]<=0) + int(eggs[j][0]<=0) ) # 충돌 계산하기
        flag = True
        # 충돌 원상 복귀
        eggs[idx] =eggs[idx] +eggs[j][1]
        eggs[j] =eggs[j] +eggs[idx][1]
    # 한 번도 안 깨짐 -> 선택한 idx 내려두고 다음 idx +1 로 이동  
    if not flag : 
      backtracking(idx+1 , cnt )

  return 0 

backtracking(0 ,0)
print(max_cnt)