[백준 Gold V] 계란으로 계란치기 - 16987

문제 설명

원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지 부엌의 대리석을 이용해 계란을 깨면 늘 껍데기가 산산조각나 뒷처리가 너무 어렵게 되곤 한다. 어떻게 하면 계란을 조심스럽게 깰 수 있을까 고민하던 인범이에게 유현이는 굉장히 좋은 해결책을 알려주었다. 바로 계란으로 계란을 치는 것이다. 계란끼리 부딪쳐보니 껍데기가 아주 예쁘게 갈라지는 것을 발견한 인범이는 앞으로 계란으로 계란을 쳐서 식사 준비를 해야겠다고 생각했다. 유현이는 더 나아가 식사 준비를 할 때에도 두뇌를 단련할 수 있는 좋은 퍼즐을 인범이에게 알려주었다.

문제를 소개하기 전, 계란으로 계란을 치게 될 경우 어떤 일이 벌어지는지를 먼저 이해하고 가자. 각 계란에는 내구도와 무게가 정해져있다. 계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎이게 된다. 그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 된다. 예를 들어 계란 1의 내구도가 7, 무게가 5이고 계란 2의 내구도가 3, 무게가 4라고 해보자. 계란 1으로 계란 2를 치게 되면 계란 1의 내구도는 4만큼 감소해 3이 되고 계란 2의 내구도는 5만큼 감소해 -2가 된다. 충돌 결과 계란 1은 아직 깨지지 않았고 계란 2는 깨졌다.

유현이가 인범이에게 알려준 퍼즐은 일렬로 놓여있는 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제였다. 구체적으로 계란을 치는 과정을 설명하면 아래와 같다.

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

이 과정을 통해 최대한 많은 계란을 깨는 것이 앞으로 인범이가 매일 아침마다 풀게 될 퍼즐이다. 그리고 유현이는 인범이가 찾은 답이 정답이 맞는지 확인해주려고 한다. 일렬로 놓인 계란들의 내구도와 무게가 차례대로 주어졌을 때 최대 몇 개의 계란을 깰 수 있는지 알아맞춰보자.

입력

첫째 줄에 계란의 수를 나타내는 N(1 ≤ N ≤ 8)가 주어진다. 그 다음 N개의 줄에는 계란의 내구도와 무게에 대한 정보가 주어진다. i+1번째 줄에는 왼쪽에서 i번째에 위치한 계란의 내구도 Si(1 ≤ Si ≤ 300)와 무게 Wi(1 ≤ Wi ≤ 300)가 한 칸의 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 인범이가 깰 수 있는 계란의 최대 개수를 출력한다.

 

---

 

첫번째 시도

# 계란으로 계란을 칠 때
# 내구도는 상대 계란의 무게만큼 깍임 => 0이하 되는 순간 깨짐
# 예) 계란1 내구도 7, 무게 5
# 계란2 내구도 3, 무게 4
# 계란1 -> 계란2 : 계란 2 깨짐
# 왼쪽부터 한번씩 다른 계란을 쳐 최대한 많은 계란을 깨는 문제
# 가장 왼쪽 계란 들기
# 다른 계란 하나 선택해서 치기
# 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 넘어감
# 가장 최근에 든 계란의 오른쪽 계란을 드고 2번 진행 => 재귀함수로 구현


from sys import stdin

N = int(input()) # 계란의 수

# 계란의 내구도와 무게에 대한 정보 => 리스트에 담기
# 문자열로 입력받기
egg_list = [list(map(int, stdin.readline().split())) for _ in range(N)]

answer = 0

# 계란 치기
def crackedEgg(egg_list):
    global answer
    count = 0
    for egg in egg_list:
        if egg[0] <= 0:
            count += 1
    answer = max(answer, count)

# equence = 순서 / egg_list = 리스트에 담은 계란들
def solution(sequence, egg_list):
    global answer

    # 계란이 가장 오른쪽에 위치한 계란인 경우 계란치기 종료
    if sequence == N:
        crackedEgg(egg_list)
        return
    
    # 손에 든 계란 깨지면 다음 계란을 선택 후 진행
    if egg_list[sequence][0] <= 0:
        solution(sequence + 1, egg_list) # 재귀함수
        return
    
    # 깨지지 않은 계란이 없으면 함수 계란치기 종료
    check = True
    for i in range(N):
        if sequence == i: continue
        if egg_list[i][0] > 0: check = False
    if check:
        crackedEgg(egg_list)
        return
    
    # 손에 든 계란으로 안 깨진 계란 치기
    for i in range(N):
        if i == sequence: continue
        if egg_list[i][0] <= 0 : continue

        # 계란 치기
        egg_list[sequence][0] -= egg_list[i][1]
        egg_list[i][0] -= egg_list[sequence][1]
        solution(sequence + 1, egg_list)

        # 깨지지 않은 경우 다시 복구
        egg_list[sequence][0] += egg_list[i][1]
        egg_list[i][0] += egg_list[sequence][1]


solution(0, egg_list)
print(answer)

 

실패...

런타임 에러에는 여러 종류가 있는데,

이 에러는 로컬 변수를 할당하기 전에 참조했을 때 발생하는 오류이며, 주로 함수 내부에서 변수를 잘못 사용했을 때 발생한다.

(자세한 설명: https://gr-st-dev.tistory.com/1897)

 

그래서 전역 변수로 다시 설정하면서 코드를 좀 수정했다.

 

 

두번째 시도

n = int(input())
egg_list = []

for _ in range(n):
    s, w = map(int, input().split())
    egg_list.append([s, w])

answer = 0

def crackedEgg(sequence):
    global answer
    if sequence == n:
        count = 0
        for i in range(n):
            if egg_list[i][0] <= 0:
                count += 1
        answer = max(count, answer)
        return
    
    # 손에 있는 계란이 깨지면 다른 계란 선택
    if egg_list[sequence][0] <= 0:
        crackedEgg(sequence + 1)
        return
    
    checkEgg = True # 계란이 모두 깨졌는가

    for i in range(n):
        if i == sequence:
            continue
        if egg_list[i][0] > 0:
            checkEgg = False
            break

    # 다 깨져 있는 경우 종료
    if checkEgg:
        answer = max(answer, n - 1)
        return
    
    # 계란 치기
    for i in range(n):
        if i == sequence: continue
        if egg_list[i][0] <= 0:
            continue

         # 계란 치기
        egg_list[sequence][0] -= egg_list[i][1]
        egg_list[i][0] -= egg_list[sequence][1]
        crackedEgg(sequence + 1)

        # 깨지지 않은 경우 다시 복구
        egg_list[sequence][0] += egg_list[i][1]
        egg_list[i][0] += egg_list[sequence][1]

crackedEgg(0) # index[0] 부터 시작
print(answer)

 

드디어 맞았다...!!

 

 

 

 

아래는 내가 문제 자체를 이해하려고 했던 흔적들...ㅋㅋㅋ

계란1: 내구도 8, 무게 5
계란2: 내구도 1, 무게 100
계란3: 내구도 3, 무게 5

8 - 100 => 계란1 깨짐
계란2가 가장 왼쪽
1 - 5 => 계란2 깨짐
계란 3이 남음

8 - 5 => 계란1 내구도 3 / 계란3 내구도 -2
계란3 깨짐 / 계란1 계속 이어짐
3 - 100 => 계란1 내구도 -97 / 계란2 1 - 5 = -4
둘다 깨짐





====
가장 오른쪽에 위치한 계란일 경우 계란 치기 종료

손에 든 계란 깨지면 다음 계란을 선택 후 진행

깨지지 않은 계란이 없으면 함수 계란치기 종료

 

 

문제를 푸는 시간만큼 이해하는 데 오래 걸렸던 문제다.

나중에 내가 잘 풀 수 있을까 싶다...ㅠ

알고리즘 열심히 해야지...)