📌 문제 정보

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

유형: 백트래킹

난이도: 골드5

스스로 풀었는가? ✅

💻 작성 코드

import sys

readline = sys.stdin.readline
eggNum = int(readline())
egg_hps = []
egg_weights = []
answer = 0

def back(cnt):
    global answer
    if cnt == eggNum:
        broken_eggs = [hp for hp in egg_hps if hp <= 0]
        answer = max(answer, len(broken_eggs))
        return
    
    if egg_hps[cnt] <= 0:
        back(cnt + 1)
    else:
        is_hit = False
        for idx in range(eggNum):
            if egg_hps[idx] > 0 and egg_hps[cnt] > 0 and idx != cnt:
                is_hit = True
                egg_hps[cnt] -= egg_weights[idx]
                egg_hps[idx] -= egg_weights[cnt]
                back(cnt + 1)
                egg_hps[cnt] += egg_weights[idx]
                egg_hps[idx] += egg_weights[cnt]
        if not is_hit:
            back(cnt + 1)
            
for _ in range(eggNum):
    hp, weight = map(int, readline().split())
    egg_hps.append(hp)
    egg_weights.append(weight)

back(0)
print(answer)

🎯 접근 방식

1. 앞에서부터 계란을 하나씩 든다.
2. 만약 계란이 깨져있다면, 다음 계란으로 넘어간다.
3. 계란이 깨져있지 않다면, 계란 정보를 순회하면서 해당 계란과 부딪힐 수 있는 계란을 하나씩 부딪힌다.
4. 부딪힐 계란이 없다면 다음 계란으로 넘어간다. (현재 들고 있는 계란 빼고 다른 계란이 모두 깨진 경우)
5. 모든 계란을 한번씩 들었다면 깨진 계란의 개수를 센다.

💡 개선사항

1. 튜플이나 이차원 리스트를 이용해 hp와 weigh를 하나의 변수로 관리
2. 들고 있는 계란과 부딪힐 계란이 하나도 없다는 것은, 다른 계란이 모두 깨졌다는 의미이므로 다음 계란이 아니라 바로 조건 카운트로 넘어가도 된다.

문제를 잘 읽자.. 깨려는 계란도 hp > 0이여야 하는 것, 부딪히면 서로 데미지를 받는다는 걸 처음에 생각하지 못했다.

[ktb-algorithm-study] 3주차