문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
16987번: 계란으로 계란치기 문제 보러 가기
제한시간: 2초
메모리 제한: 512 MB
문제
계란으로 계란을 치게 될 경우 어떤 일이 벌어지는지를 먼저 이해하고 가자. 각 계란에는 내구도와 무게가 정해져있다. 계란으로 계란을 치게 되면 각 계란의 내구도는 상대 계란의 무게만큼 깎이게 된다. 그리고 내구도가 0 이하가 되는 순간 계란은 깨지게 된다. 예를 들어 계란 1의 내구도가 7, 무게가 5이고 계란 2의 내구도가 3, 무게가 4라고 해보자. 계란 1으로 계란 2를 치게 되면 계란 1의 내구도는 4만큼 감소해 3이 되고 계란 2의 내구도는 5만큼 감소해 -2가 된다. 충돌 결과 계란 1은 아직 깨지지 않았고 계란 2는 깨졌다.
유현이가 인범이에게 알려준 퍼즐은 일렬로 놓여있는 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제였다. 구체적으로 계란을 치는 과정을 설명하면 아래와 같다.
- 가장 왼쪽의 계란을 든다.
- 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
- 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.
이 과정을 통해 최대한 많은 계란을 깨는 것이 앞으로 인범이가 매일 아침마다 풀게 될 퍼즐이다. 그리고 유현이는 인범이가 찾은 답이 정답이 맞는지 확인해주려고 한다. 일렬로 놓인 계란들의 내구도와 무게가 차례대로 주어졌을 때 최대 몇 개의 계란을 깰 수 있는지 알아맞춰보자.
입력
첫째 줄에 계란의 수를 나타내는 N(1 ≤ N ≤ 8)가 주어진다. 그 다음 N개의 줄에는 계란의 내구도와 무게에 대한 정보가 주어진다. i+1번째 줄에는 왼쪽에서 i번째에 위치한 계란의 내구도 Si(1 ≤ Si ≤ 300)와 무게 Wi(1 ≤ Wi ≤ 300)가 한 칸의 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 인범이가 깰 수 있는 계란의 최대 개수를 출력한다.
예제 입력 1
3
8 5
1 100
3 5
예제 출력 1
3
예제 입력 2
3
1 100
8 5
3 5
예제 출력 2
2
먼저 문제를 이해해보자.
(8,5)인 계란으로 (3,5)인 계란을 치면 1번 계란 (8,5)->(8-5=3,5), 3번 계란 (3-5=-2,5)로 하나가 깨진다.
다음 1번 계란을 다시 제자리에 두고 2번계란을 두고 남은 계란 중 하나를 친다. 그게 1번계란이다.
그럼 1번 계란은 (3,5)->(3-100=-97,5)가 되어 깨지고, 2번 계란은 (1-5=-4,100)이 되어 깨진다.
3개가 모두 깨졌다.
조합의 느낌이 많이 들며 조합으로 최대 몇개까지 깰 수 있는지 확인 하는 문제로 조합으로 진행되다 조건에 맞으면 확인을 그만두는 백트래킹 문제임을 딱 알 수 있다.
기존의 백트래킹 문제처럼 패턴화가 되었지만 depth가 도달 했을 때 조건 말고도 많은 조건들을 고려해야한다.
확실히 어려운 문제이다.
정답답 코드
import sys
sys.setrecursionlimit(10000)
input=sys.stdin.readline
def DFS(L):
global cnt
if L==N: # 모든 계란을 다 살펴 봤을때
broken=0
for i in range(N): # 계란이 몇개 깨졌는지 확인하기
if eggs[i][0]<=0: # 계란들중에 깨진것들
broken+=1 # 카운트
cnt=max(cnt,broken)
return
else:
# 1. 현재 계란이 이미 깨졌을때
if eggs[L][0]<=0:
DFS(L+1) # 다음 계란 들기
return
# 2. 자신을 제외한 깨지지 않은 계란이 하나도 없으면. 즉, 자기빼고 이미 다 깨져있으면
check=True
for i in range(N):
if i==L: # 자기가 자기 깨거나 자기가 깨졌는지 확인할 필요없음
continue
if eggs[i][0]>0: # 자기를 제외한 깨지지 않은 계란이 하나라도 있으면
check=False
break
if check: #다 깨져있는 경우
cnt=max(cnt , N-1) # 자기 하나 빼고 이미 다 깨져버려서 생각 할 필요없이 N-1
return
# 3. 1.도 2.도 아니면 다른 계란끼리 조합을 통해 깨본다.
for i in range(N):
if i==L or eggs[i][0]<=0: # 현재 계란이 현재 계란이거나 이미 깨져있으면
continue # 넘어감
eggs[L][0]-=eggs[i][1] # 현재 계란에서 다른 계란 때림
eggs[i][0]-=eggs[L][1]
DFS(L+1)
eggs[L][0]+=eggs[i][1]
eggs[i][0]+=eggs[L][1]
if __name__=="__main__":
N=int(input())
eggs=[list(map(int, input().split())) for _ in range(N)] #내구도와 무게
cnt=0
DFS(0)
print(cnt)
이걸 코테 때 저렇게 모든 경우를 다 고려 해서 풀 수 있을까....?
