[백준 16987] 계란으로 계란치기(JAVA/C++)

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

 

 

이 문제도 이전에 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;
}