Sign in Subscribe
PS

[PS] BOJ 16987 / 계란으로 계란치기

Minjun Kim

• 4 min read
[PS] BOJ 16987 / 계란으로 계란치기
Thumbnail: Photo by Mockup Graphics (Unsplash)
문제 링크: https://www.acmicpc.net/problem/16987

계란 프라이가 먹고 싶은 밤입니다. 백트래킹으로 가능한 모든 경우를 탐색해 최댓값을 찾으면 됩니다.

풀이

문제 조건 분석하기

계란으로 계란을 치는 과정은 다음과 같습니다.

  1. 가장 왼쪽의 계란을 든다.
  2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
  3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

0번 계란부터 $N-1$번 계란까지 하나씩 들면서 다른 계란들 중 깨지지 않은 것을 하나 골라 치는 과정을 반복해주면 됩니다.

계란을 치다

이때, "계란을 친다" 라는 과정은 다음과 같이 정의됩니다.

두 계란 $a, b$에 대해, 각각의 내구도를 $D_a, D_b$라 하고 무게를 $W_a, W_b$입니다.
계란 $a$로 $b$를 치면, 각각의 무게는 다음과 같이 변합니다:

$D_a = D_a - W_b$, $D_b = D_b - W_a$

백트래킹 유망성 판단하기

백트래킹이란, DFS 등의 그래프 탐색을 진행하되 유망하지 않은 분기는 즉시 탐색을 중단하는 방법입니다.

따라서, 각 분기가 유망한지 아닌지를 판단하기 위한 조건이 필요합니다. 이 문제의 경우 다음의 경우는 더 탐색하지 않아도 됩니다:

들고 있는 계란 $h$와 치려는 계란 $i$에 대해,

  • $i$가 이미 깨진 상태일 때
  • $i = h$일 때 (자기 자신을 칠 수 없다.)

백트래킹

이제 백트래킹을 구현하면 됩니다.

구현 시 주의할 점은 다음과 같습니다.

  • 계란의 남은 내구도가 0 이하일 때 깨진 상태입니다.
  • 계란은 왼쪽에서부터 순서대로 하나씩 손에 듭니다.
  • 손에 들고 있는 계란으로 깨지지 않은 다른 계란을 1 개만 칩니다.
  • 손에 들고 있는 계란이 이미 깨져 있거나, 다른 모든 계란이 깨져 있는 경우는 치지 않고 넘어갑니다.
    • 이외의 경우에는 반드시 계란을 1개 쳐야 합니다.
EGGS = list(list(map(int, input().split())) for _ in range(N))
# EGGS = [DURABILITY, WEIGHT]
DURABILITY = 0
WEIGHT = 1

def dfs(holding):
    if holding == N: # 가장 오른쪽에 위치한 계란을 들 때 종료
        cnt = 0
        for egg in EGGS:
            if egg[DURABILITY] <= 0:
                cnt += 1
        return cnt
    
    if EGGS[holding][DURABILITY] <= 0:
        return dfs(holding + 1)
    
    cnt = 0
    hit = False
    # 다른 계란을 치는 경우
    for i in range(N):
        cur_durability, cur_weight = EGGS[holding]
        other_durability, other_weight = EGGS[i]
        # 들고있는 계란을 치는 경우 / 치려는 계란이 이미 깨진 경우는 DFS를 진행하지 않는다.
        if i == holding or other_durability <= 0: 
            continue

        EGGS[holding][DURABILITY] -= other_weight
        EGGS[i][DURABILITY] -= cur_weight
        hit = True
        res = dfs(holding + 1)
        if res > cnt:
            cnt = res
        EGGS[holding][DURABILITY] = cur_durability
        EGGS[i][DURABILITY] = other_durability
    
    # 아무것도 깨지 않고 다음 계란으로 넘어갔을 경우
    if not hit:
        res = dfs(holding + 1)
        if res > cnt:
            cnt = res
    return cnt

백트래킹

전체 코드

input = open(0).readline
N = int(input())
EGGS = list(list(map(int, input().split())) for _ in range(N))
# EGGS = [DURABILITY, WEIGHT]
DURABILITY = 0
WEIGHT = 1

def dfs(holding):
    if holding == N: # 가장 오른쪽에 위치한 계란을 들 때 종료
        cnt = 0
        for egg in EGGS:
            if egg[DURABILITY] <= 0:
                cnt += 1
        return cnt
    
    if EGGS[holding][DURABILITY] <= 0:
        return dfs(holding + 1)
    
    cnt = 0
    hit = False
    # 다른 계란을 치는 경우
    for i in range(N):
        cur_durability, cur_weight = EGGS[holding]
        other_durability, other_weight = EGGS[i]
        # 들고있는 계란을 치는 경우 / 치려는 계란이 이미 깨진 경우는 DFS를 진행하지 않는다.
        if i == holding or other_durability <= 0: 
            continue

        EGGS[holding][DURABILITY] -= other_weight
        EGGS[i][DURABILITY] -= cur_weight
        hit = True
        res = dfs(holding + 1)
        if res > cnt:
            cnt = res
        EGGS[holding][DURABILITY] = cur_durability
        EGGS[i][DURABILITY] = other_durability
    
    # 아무것도 깨지 않고 다음 계란으로 넘어갔을 경우
    if not hit:
        res = dfs(holding + 1)
        if res > cnt:
            cnt = res
    return cnt

print(dfs(0))

solution.py