[백준] 16987번 : 계란으로 계란치기
문제 푼 날짜 : 2021-12-03
문제
문제 링크 : https://www.acmicpc.net/problem/16987
접근 및 풀이
문제가 이해가 안돼서 푸는 데 좀 오래걸린 문제였다.
백트래킹을 이용하였고, 매개변수로 각 계란의 index값(코드 내의 idx 변수)을 넘겨주었다.
이 때, idx는 손에 쥔 계란의 index를 뜻하며, 마지막 계란을 쥐었을 때 깨진 계란의 개수를 세어주었다.
깰 계란이 없을 때 마지막 계란을 들게하는 것이 포인트였다.(라고 개인적으로 생각한다...)
코드
// 백준 16987번 : 계란으로 계란치기
#include <bits/stdc++.h>
using namespace std;
int N, ans = -1;
vector<pair<int, int>> v;
void dfs(int idx) {
if (idx == N) {
int cnt = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i].first <= 0) {
cnt++;
}
}
ans = max(ans, cnt);
return;
}
if (v[idx].first <= 0) { // 손에 쥔 계란이 깨진 경우
dfs(idx + 1);
} else {
bool broken = false;
for (int j = 0; j < v.size(); j++) {
if (j == idx || v[j].first <= 0) { // 손에 쥔 계란, 깨진 계란 pass
continue;
}
broken = true;
v[j].first -= v[idx].second;
v[idx].first -= v[j].second;
dfs(idx + 1);
v[j].first += v[idx].second;
v[idx].first += v[j].second;
}
if (!broken) { // 깰게 없으면 마지막 계란으로
dfs(N);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
v.push_back(make_pair(a, b));
}
dfs(0);
cout << ans;
return 0;
}
결과
// 백준 16987번 : 계란으로 계란치기
#include <bits/stdc++.h>
using namespace std;
int N, ans = -1;
vector<pair<int, int>> v;
void dfs(int idx) {
if (idx == N) {
int cnt = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i].first <= 0) {
cnt++;
}
}
ans = max(ans, cnt);
return;
}
if (v[idx].first <= 0) { // 손에 쥔 계란이 깨진 경우
dfs(idx + 1);
} else {
bool broken = false;
for (int j = 0; j < v.size(); j++) {
if (j == idx || v[j].first <= 0) { // 손에 쥔 계란, 깨진 계란 pass
continue;
}
broken = true;
v[j].first -= v[idx].second;
v[idx].first -= v[j].second;
dfs(idx + 1);
v[j].first += v[idx].second;
v[idx].first += v[j].second;
}
if (!broken) { // 깰게 없으면 마지막 계란으로
dfs(N);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
v.push_back(make_pair(a, b));
}
dfs(0);
cout << ans;
return 0;
}
피드백
다시 열심히 하자.
Author And Source
이 문제에 관하여([백준] 16987번 : 계란으로 계란치기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bestcoders/백준-16987번-계란으로-계란치기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)