문제 이해 단계
https://www.acmicpc.net/problem/16987
16987번: 계란으로 계란치기
원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱
www.acmicpc.net
N개의 계란이 존재하고,
각 계란에는 (내구도, 무게) 정보가 쌍으로 주어진다.그리고 두 계란이 부딪힐 때
서로의 무게만큼 내구도가 깎여나간다. 내구도가 0 이하가 되면 계란이 깨지는 것으로 간주한다.
그리고 계란을 깨는 과정은 아래와 같이 한다.
1.
가장 왼쪽의 계란을 든다.
2.
손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다.
단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다.
이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3.
가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고
2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우
계란을 치는 과정을 종료한다.
이러한 과정으로 계란을 깰 때
최대 몇 개의 계란을 깰 수 있는지 찾는 문제
문제 접근 단계
일단 최대 계란의 개수가 8개밖에 안된다.
엄청나게 적다.완전탐색이 무조건 가능하다.
이 가능성을 열어두고 시작한다.
그리고 계란을 순서대로 깨야하기 때문에 정렬을 할 수는 없다.
때문에 그리디는 아니다.
아마 가장 왼쪽에 있는 계란부터 순차적으로
다른 계란과 부딪혀보는 것을 직접 해봐야 할 것 같다.
그런데 계란이 최대 8개밖에 안되기 때문에 모든 경우의 수를 다 살펴봐서
혹시 최악의 경우 N! 이 나온다고 해도
8! = 40320이라서 1초가 넘지 않아서 가능하다.
그래서 이 문제를 백트래킹을 통해
모든 경우의 수를 다 살펴볼 것이다.
백트래킹 방식
일반적인 백트래킹과는 조금 다르게 구성해야 한다.
왜냐하면 순차적으로 계란을 들었을 때,
다른 계란과 부딪히는 모든 경우의 수를 체크해줘야 하기 때문이다.
예를 들면 아래 그림과 같다.
만약 위와 같은 경우가 나온다고 가정해 보자.
첫 번째 계란을 들었을 때,
3번째와 4번째를 깨고 첫 번째 계란이 깨졌다.
그리고 두 번째 계란으로
4번째 계란을 깨는 행동으로 이어졌다고 하자.
첫 번째 계란이 선택하는 계란의 경우의 수가 바뀌자,
두 번째 계란을 들었을 때
선택할 수 있는 경우의 수가 바뀌었다.
이렇게, 손에 든 계란이 어떤 계란이 어떤 계란과 부딪혔는지도,
각각 다른 경우로 체크해 줘 재귀함수를 호출해줘야 한다.
자세한 것은 코드로 설명하겠다.
문제 구현 단계
#include <iostream>
using namespace std;
struct Egg{
int hp; // 내구도
int w; // 무게
};
int N;
Egg egg[10]; // 계란
int ans; // 깨진 개수
// x -> 현재 들고 있는 계란 번호
void backTracking(int x){
if(x > N+1) return;
// 1 ~ N개의 계란을 모두 탐색(부딪히게 함)
for(int i = 1; i <= N; i++){
// 들고 있는 계란이 이미 깨져 있으면 오른쪽 계란으로 백트래킹
if(egg[x].hp <= 0) backTracking(x+1);
// 자기 자신이랑 이미 깨진 계란은 패스
else if(x == i || egg[i].hp <= 0) continue;
else{
// 부딪힘
egg[x].hp -= egg[i].w;
egg[i].hp -= egg[x].w;
backTracking(x+1); // 해당 계란과 부딪힌 경우 백트래킹
// 원상복구
egg[x].hp += egg[i].w;
egg[i].hp += egg[x].w;
}
}
int tmp = 0;
// 깨진 계란의 개수 세어줌
for(int i = 1; i<= N; i++){
if(egg[i].hp <= 0) tmp++;
}
//최댓값 정답 저장
ans = max(ans,tmp);
}
int main()
{
cin >> N;
for(int i = 1; i <= N; i++) {
int v1, v2;
cin >> v1 >> v2;
egg[i] = {v1,v2};
}
backTracking(1);
cout << ans;
}전체 코드이다. Backtracking의 매개변수는
현재 손에 들고 있는 계란의 번호이다.
백트래킹을 전체적으로 1~N까지
모든 계란과 부딪히게 반복문을 돌렸다.
그리고 자기 자신과 깨진 계란을 제외하게끔 만들었다.
나머지는 주석으로 다 이해될 것인데,
여기서 한 가지 왜 if(x > N+1) return인지에 대해서이다.
계란의 범위는 1 ~ N까지이다.
그럼 x > N 일 때 종료하는 것이 맞지 않나?
이는 마지막에 깨진 계란의 횟수를
확실하게 세어주기 위함이다.
만약 x > N+1에서 반환된다면
돌아온 함수에서는 x = N+1일 것이다.
그럼 egg [N+1]. hp은 무조건 0이니 반복문을 continue 하여
더 이상 백트래킹 없이 반복문을 탈출하게 된다.
그렇게 더 이상의 비교 없이 안전하게 깨진 계란을 구할 수 있다.
풀이는 여기까지이다.
나머지는 주석으로 이해가 되길 바란다.
시행착오
백트래킹 문제인 것은 바로 알아차렸으나,
평소에 하던 방식이 아니어서 풀지 못했다.
이중 반복으로도 풀어보고,
혹시나 백트래킹이 아닌가 DP로도 해보고 다 했는데
2시간 정도 해보고 더 이상 안 되겠어서 포기했다.
아직 많이 모자란 것 같다.인터넷을 참고하고도 이렇게 센스 있게 푸는 것을 할 자신은 없는데..
대체 실력은 언제 늘지
생활비..