링크 →

16987번: 계란으로 계란치기

• 아영

  • 코드

  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  
  public class boj16987 {
      static int N,answer;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          N = Integer.parseInt(br.readLine());
  
          boolean[] broken = new boolean[N];
          StringTokenizer st;
          List<int[]> eggs = new ArrayList<>();
  
          for (int i = 0; i < N; i++) {
              st = new StringTokenizer(br.readLine());
              eggs.add(new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
          }
          dfs(0,0,eggs);
  
          System.out.println(answer);
  
      }
      //egg[0] : 내구성 egg[1] : 무게
      private static void dfs(int now,int cnt,List<int[]>eggs){
          if(now==N){
              if(cnt>answer) answer = cnt;
              return;
          }
          //판에있는 계란이 내가갖고있는 계란빼고 다 깨져있거나 or 내가들고있는 계란이 깨져있는 경우
          if(cnt>=N-1||eggs.get(now)[0]<=0){
              dfs(now+1,cnt,eggs);
          }else{
              for (int i = 0; i < eggs.size(); i++) {
                  //내가 들고있는 계란이 있는 위치를 가리키는 경우
                  if(i==now) continue;
                  int[] egg_onHand = eggs.get(now);
                  int[] egg = eggs.get(i);
                  //판에 있는 계란이 깨져있는 경우, 다음 계란을 선택함
                  if(egg[0]<=0) continue;
  
                  int broke_cnt = 0;
                  egg_onHand[0]-= egg[1];
                  egg[0]-= egg_onHand[1];
  
                  if(egg_onHand[0]<=0) broke_cnt+=1;
                  if(egg[0]<=0)broke_cnt+=1;
  
                  dfs(now + 1, cnt + broke_cnt,eggs);
                  egg_onHand[0]+=egg[1];
                  egg[0]+=egg_onHand[1];
              }
          }
  
      }
  }
  

  • 시간,메모리

  

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class baekjoon16987 {
  
  	static int N,ans=0,cnt=0;
  	static Egg[] egg;
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st;
  		N = Integer.parseInt(br.readLine());
  		egg = new Egg[N];
  		for (int i = 0; i < N; i++) {
  			st = new StringTokenizer(br.readLine()+" ");
  			int d = Integer.parseInt(st.nextToken());
  			int w = Integer.parseInt(st.nextToken());
  			egg[i] = new Egg(d, w);
  		}
  		
  		func(0);
  		System.out.println(ans);
  	}
  	private static void func(int idx) {
  		if(idx==N) {
  			ans = Math.max(ans, cnt);
  			return;
  		}
  		if(egg[idx].dur<=0 || cnt==N-1) {
  			func(idx+1);
  			return;
  		}
  		int count=cnt;
  		for (int i = 0; i < egg.length; i++) {
  			if(i==idx) continue;
  			if(egg[i].dur<=0)continue;
  			
  			egg[idx].dur -=egg[i].weight;
  			egg[i].dur -=egg[idx].weight;
  			
  			if(egg[idx].dur<=0) {
  				cnt++;
  			}
  			if(egg[i].dur<=0) {
  				cnt++;
  			}
  			
  			func(idx+1);
  			egg[idx].dur +=egg[i].weight;
  			egg[i].dur +=egg[idx].weight;
  			cnt=count;
  			
  		}
  	}
  }
  
  class Egg{
  	int dur;
  	int weight;
  	public Egg(int dur, int weight) {
  		this.dur = dur;
  		this.weight = weight;
  	}
  }
  

  • 시간,메모리

  

• 건

  • 코드
  • 시간,메모리

• 용문

  • 코드

  class BJ16987 {
      
      private var N = 0
      private var shields: [Int] = []
      private var weights: [Int] = []
      
      private var answer = 0
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          self.N = Int( readLine()! )!
          
          for _ in 0..<N {
              let temp = readLine()!.split(separator: " ").map{ Int($0)! }
              shields.append(temp[0])
              weights.append(temp[1])
          }
      }
      
      private func calc() {
          dfs(0)
      }
      
      private func dfs(_ index: Int) {
          if index >= N {
              var count = 0
              for sheild in shields {
                  if sheild <= 0 {
                      count += 1
                  }
              }
              answer = max(answer, count)
              return
          }
          
          var flag = false
          
          for i in 0..<N {
              if i == index { continue }
              
              if shields[i] > 0, shields[index] > 0 {
                  flag = true
                  shields[index] -= weights[i]
                  shields[i] -= weights[index]
                  dfs(index + 1)
                  shields[index] += weights[i]
                  shields[i] += weights[index]
              }
          }
          if !flag {
              dfs(index + 1)
          }
      }
      
      private func printAnswer() {
          print(answer)
      }
  }
  
  BJ16987().solve()
  

  • 시간,메모리