링크 →

18429번: 근손실

• 아영

  • 코드

  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class boj18429 {
      static int answer = 0;
      static int N,K;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          N = Integer.parseInt(st.nextToken());
          K = Integer.parseInt(st.nextToken());
          int[] kits = new int[N];
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              kits[i] = Integer.parseInt(st.nextToken());
          }
          boolean[] checked = new boolean[N];
          dfs(500,kits,checked,0);
          System.out.println(answer);
      }
  
      private static void dfs(int now,int[] kits,boolean[] checked,int cnt){
          if(cnt==N){
              answer+=1;
              return;
          }
  
          for (int i = 0; i < N; i++) {
              if(checked[i]) continue;
              int weight = now+kits[i]-K;
              if(weight>=500){
                  checked[i] = true;
                  dfs(weight,kits,checked,cnt+1);
                  checked[i] = false;
              }
          }
      }
  
  }
  

  • 시간,메모리

  

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class Main {
  	static int N,K,ans=0;
  	static int[] weight,arr;
  	static boolean visit[];	
  	public static void main(String[] args) throws IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine()+" ");
  		
  		N = Integer.parseInt(st.nextToken());
  		K = Integer.parseInt(st.nextToken());
  		
  		weight= new int[N];
  		arr= new int[N];
  		visit= new boolean[N];
  		st = new StringTokenizer(br.readLine()+" ");
  		for (int i = 0; i < N; i++) {
  			weight[i] = Integer.parseInt(st.nextToken());
  		}
  		
  		func(0);
  		System.out.println(ans);
  	}
  	private static void func(int cnt) {
  		int sum=500;
  		if(cnt==N) {
  			for (int i = 0; i < N; i++) {
  				sum+=arr[i]-K;
  				if(sum<500) {
  					break;
  				}
  			}
  			if(sum>=500) {
  				ans++;
  			}
  			return;
  		}
  		for (int i = 0; i < N; i++) {
  			if(!visit[i]) {
  				visit[i] = true;
  				arr[cnt] = weight[i];
  				func(cnt+1);
  				visit[i] = false;
  			}
  		}
  		
  	}
  }
  

  • 시간,메모리

  

• 건

  • 코드

  package day_0509;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class BOJ18249 {
  
  	static int n, k, answer;
  	static int[] kit;
  	static boolean[] isVisited;
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk = new StringTokenizer(br.readLine());
  		
  		n = Integer.parseInt(stk.nextToken());
  		k = Integer.parseInt(stk.nextToken());
  		
  		kit = new int[n];
  		isVisited = new boolean[n];
  		
  		stk = new StringTokenizer(br.readLine());
  		for (int i = 0; i < n; i++) {
  			kit[i] = Integer.parseInt(stk.nextToken());
  		}
  		
  		permu(0, 500);
  		
  		System.out.println(answer);
  	}
  	
  	static void permu(int cnt, int weight) {
  		if (cnt == n) {
  			answer++;
  			return;
  		}
  		
  		for (int i = 0; i < n; i++) {
  			if (!isVisited[i] && (weight - k + kit[i] >= 500)) {
  				isVisited[i] = true;
  				permu(cnt+1, weight - k + kit[i]);
  				isVisited[i] = false;
  			}
  		}
  	}
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ18429 {
      
      private var N = 0
      private var K = 0
      private var machines: [Int] = []
      
      private var answer = 0
      private var selected: [Bool] = []
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          let temp = readLine()!.split(separator: " ").map { Int($0)! }
          self.N = temp[0]
          self.K = temp[1]
          
          self.machines = readLine()!.split(separator: " ").map { Int($0)! }
          self.selected = .init(repeating: false, count: self.N)
      }
      
      private func calc() {
          permutation(weight: 500, count: 0)
      }
      
      private func permutation(weight: Int, count: Int) {
          if count == N - 1 {
              answer += 1
              return
          }
          
          for index in machines.indices {
              if selected[index] { continue }
              selected[index] = true
              if weight - K + machines[index] >= 500 {
                  permutation(weight: weight - K + machines[index], count: count + 1)
              }
              selected[index] = false
          }
      }
      
      private func printAnswer() {
          print(answer)
      }
  }
  
  BJ18429().solve()
  

  • 시간,메모리