문제
16987번: 계란으로 계란치기
원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하는데, 인범이는 힘이 너무 넘치는 나머지 부엌의 대리석을 이용해 계란을 깨면 늘 껍데기가 산산조각나 뒷처리가 너무 어렵게 되곤 한다. 어떻게 하면 계란을 조심스럽게 깰 수 있을까 고민하던 인범이에게 유현이는 굉장히 좋은 해결책을 알려주었다. 바로 계란으로 계란을 치는 것이다. 계란끼리 부딪쳐보니 껍데기가 아주 예쁘게 갈라지는 것을 발견한 인범이는 앞으로 계란으로 계란을 쳐서 식사 준비를 해야겠다고 생각했다. 유현이는 더 나아가 식사 준비를 할 때에도 두뇌를 단련할 수 있는 좋은 퍼즐을 인범이에게 알려주었다.
https://www.acmicpc.net/problem/16987
정답 코드
#include <iostream>
#include <algorithm>
using namespace std;
int N; //계란의 갯수
pair<int,int> eggs[8];
// 무게가 높은 녀석은 최대한 많은 계란을 쳐야만 한다.
// 무게가 낮은 녀석은 최대한 적은 계란을 쳐야만 한다.
// 라고 생각했지만 사실 DP가 아니었던거지.
//7! 이라면? 이건 브루스포스로 풀어도 될 것 같다.
//
int max_break=0;
void break_egg(int *egg_guard,int now_idx,int break_cnt){
if (now_idx == N){
max_break = max(max_break,break_cnt);
return ;
}
if (egg_guard[now_idx] <=0){
break_egg(egg_guard,now_idx+1,break_cnt);
}
else
{
int cnt = 0;
for(int i=0;i<N;i++)
{
if (i == now_idx || egg_guard[i] <= 0)
continue;
cnt++;
egg_guard[i]-= eggs[now_idx].second;
int now_cnt = 0;
if (egg_guard[i] <= 0)
now_cnt++;
egg_guard[now_idx] -= eggs[i].second;
if (egg_guard[now_idx] <= 0)
now_cnt++;
break_egg(egg_guard,now_idx+1,break_cnt+now_cnt);
egg_guard[now_idx] +=eggs[i].second;
egg_guard[i]+= eggs[now_idx].second;
}
if (cnt == 0)
break_egg(egg_guard,now_idx+1,break_cnt);
}
}
int main(){
cin >> N;
int egg_guard[8];
for(int i=0;i<N;i++){
int guard, weight;
cin >> guard >> weight;
eggs[i]= {guard,weight};
egg_guard[i] = guard;
}
break_egg(egg_guard,0,0);
cout << max_break << "\n";
}문제 풀이의 흐름
처음에는 뭔가 계란을 치는 규칙을 찾는 문제라고 접근했다.
정렬을 하고 쳐야하나? 아니면 무조건 무거운 녀석은 많이 칠 수 있도록 조건을 세워야 하나?
또는 전체를 합해서 최대한 무게와 치는 것 사이 관계를 찾아볼까 했었다.
왜 브루스포스를 생각하지 못했냐면 7!이 아니라 8^8을 해야한다고 생각했기 때문이다.
하지만 자세히 보니 7!로 해결할 수 있는 문제였고 그 이후로는 브루스 포스로 풀면 되겠다 생각했다.
- 계란의 내구도를 가지고 다니는 배열이 있고
- 계란은 왼쪽 0번부터 n-1번 계란까지 계속해서 치는 것 이므로 현재 손에 든 계란을 now_idx라고 생각해줬다.
- 이미 계란이 깨졌다면 다음 인덱스로 넘어간다.
- 아니라면 주변 계란을 하나씩 깨본다.
- 그렇게 모든 계란을 서로서로 치는 방식으로 재귀를 짜고 최대값을 구하면 끝.
주의 할 점
#include <iostream>
#include <algorithm>
using namespace std;
int N; //계란의 갯수
pair<int,int> eggs[8];
// 무게가 높은 녀석은 최대한 많은 계란을 쳐야만 한다.
// 무게가 낮은 녀석은 최대한 적은 계란을 쳐야만 한다.
//라고 생각했지만 사실 DP가 아니었던거지.
//7! 이라면? 이건 브루스포스로 풀어도 될 것 같다.
//
int max_break=0;
void break_egg(int *egg_guard,int now_idx,int break_cnt){
if (now_idx == 8){
max_break = max(max_break,break_cnt);
return ;
}
for(int i=0;i<8;i++){
if (i == now_idx || egg_guard[i] <= 0)
continue;
if (egg_guard[now_idx] <=0)
break_egg(egg_guard,now_idx+1,break_cnt);
else
{
egg_guard[i]-= eggs[now_idx].second;
int now_cnt = 0;
if (egg_guard[i] <= 0)
now_cnt++;
egg_guard[now_idx] -= eggs[i].second;
if (egg_guard[now_idx] <= 0)
now_cnt++;
break_egg(egg_guard,now_idx+1,break_cnt+now_cnt);
egg_guard[now_idx] +=eggs[i].second;
egg_guard[i]+= eggs[now_idx].second;
}
}
}
int main(){
cin >> N;
int egg_guard[8];
for(int i=0;i<N;i++){
int guard, weight;
cin >> guard >> weight;
eggs[i]= {guard,weight};
egg_guard[i] = guard;
}
break_egg(egg_guard,0,0);
cout << max_break << "\n";
}여기서 주의할 점은 재귀 종료조건이다.
나는 여기서 처음에 이 코드로 제출을 했었다.
- 마지막 남은 계란이 깨져 있는 경우
- 마지막 남은 계란은 안 깨졌지만 다른 계란들이 다 깨진 경우
이 두가지 경우에 최댓값 갱신이 안되는 상황이 발생해서 그 경우를 해결해주고 수정해서 제출해서 맞았다.
반성 및 고찰
모의 코테셋을 풀때는 당연히 dp라고 생각했고 시간 복잡도를 제대로 계산하지 않았었다.
먼저 그런 조건을 찾기 전에 시간 복잡도를 잘 생각해서 풀이를 빠르게 떠올릴 수 있는 연습이 부족하다고 느꼈다.
앞으로는 조금 더 생각을 차근차근 해가면서 풀이를 찾았으면 좋은 실력을 쌓을 수 있을 것 같다.
화이팅!!
Uploaded by N2T