알고리즘 문제풀이/백준
[백준 16987] 계란으로 계란치기(JAVA/C++)
소보루:-)
2020. 3. 7. 22:02
https://www.acmicpc.net/problem/16987
16987번: 계란으로 계란치기
원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱걸이를 5회 하는 기적의 운동 루틴을 통해 뇌와 근육을 동시에 단련한다. 근육을 단련할 때 식단이 정말로 중요하다는 것을 아는 인범이는 탄수화물이 많은 밥이나 빵 따위의 아침 식사를 대신해 단백질이 많은 계란찜을 해먹는다. 계란찜을 먹기 위해서는 계란을 깨야 하
www.acmicpc.net
이 문제도 이전에 C++로 풀어본 문제이다.
내구성 배열(S)과 무게 배열(W)을 만들어서 내구성 배열이 0이하인 것은 깨진것으로 처리해줬다.
[JAVA]
import java.util.Scanner;
public class Main {
public static int N,ans=0;
public static int[] S,W;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
N=sc.nextInt();
S=new int[N];
W=new int[N];
for(int i=0; i<N; i++) {
int s=sc.nextInt();
int w=sc.nextInt();
S[i]=s;
W[i]=w;
}
solve(0);
System.out.println(ans);
}
private static void solve(int now) {
if(now==N) {
int cnt=0;
for(int i=0; i<N; i++) {
if(S[i]<=0) cnt++;
}
if(ans<cnt)ans=cnt;
return;
}
if(S[now]<=0) {
solve(now+1);
}else {
boolean f=false;
for(int i=0; i<N; i++) {
if(i==now || S[i]<=0) continue;
f=true;
S[i]-=W[now];
S[now]-=W[i];
solve(now+1);
S[i]+=W[now];
S[now]+=W[i];
}
if(f==false)solve(now+1);
}
}
}
[C++]
#include <iostream>
using namespace std;
int N, ans = 0;
int S[8];
int W[8];
bool Check(int index){
for (int i = 0; i <N; i++){
if (index == i) continue;
if (S[i]>0) return 1;
}
return 0;
}
void Solve(int index){
if (index == N){
int cnt = 0;
for (int i = 0; i < N; i++){
if (S[i]<=0){
cnt++;
}
}
if (ans < cnt) ans = cnt;
return;
}
if (S[index]<=0 || Check(index) == 0){
Solve(index + 1);
}
else{
for (int i = 0; i < N; i++){
if (index == i || S[i]<=0) continue;
S[index] -= W[i];
S[i] -= W[index];
Solve(index + 1);
S[index] += W[i];
S[i] += W[index];
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++){
cin >> S[i] >> W[i];
}
Solve(0);
cout << ans;
return 0;
}