링크 →

16198번: 에너지 모으기

• 아영

  • 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.StringTokenizer;
  
  public class boj16198 {
      static int answer =0;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          ArrayList<Integer> marbles = new ArrayList<>();
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              marbles.add(Integer.parseInt(st.nextToken()));
          }
          dfs(marbles,0);
          System.out.println(answer);
  
      }
  
      private static void dfs(ArrayList<Integer> marbles, int weight){
          if(marbles.size()==3){
              weight += marbles.get(0)*marbles.get(2);
              if(answer< weight) answer = weight;
              return;
          }
  
          for (int i = 1; i < marbles.size()-1; i++) {
              ArrayList<Integer> temp = (ArrayList<Integer>)marbles.clone();
              temp.remove(i);
              dfs(temp,weight+(temp.get(i-1)*temp.get(i)));
          }
      }
  
  }
  

  • 시간,메모리

  

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.StringTokenizer;
  
  public class baekjoon16198 {
  
  	static int N,ans=0;
  	static ArrayList<Integer> weight = new ArrayList<>();
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		N = Integer.parseInt(br.readLine());
  		
  		StringTokenizer st = new StringTokenizer(br.readLine()+" ");
  		for (int i = 0; i < N; i++) {
  			weight.add(Integer.parseInt(st.nextToken()));
  		}
  		
  		func(0);
  		System.out.println(ans);
  	}
  	private static void func(int sum) {
  		if(weight.size()<=2) {
  			ans=Math.max(ans, sum);
  			return;
  		}
  		for (int i = 1; i < weight.size()-1; i++) {
  			int num = weight.get(i);
  			int cal = weight.get(i-1)*weight.get(i+1);
  			weight.remove(i);
  			func(sum+cal);
  			weight.add(i,num);
  		}
  	}
  }
  

  • 시간,메모리

  

• 건

  • 코드

  package day_0509;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.StringTokenizer;
  
  public class BOJ16198 {
  	
  	static int answer;
  	static List<Integer> energy;
  	
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk = new StringTokenizer(br.readLine());
  		
  		int n = Integer.parseInt(stk.nextToken());
  		
  		energy = new ArrayList<>();
  		
  		stk = new StringTokenizer(br.readLine());
  		for (int i = 0; i < n; i++) {
  			energy.add(Integer.parseInt(stk.nextToken()));
  		}
  		
  		answer = 0;
  		dfs(n, 0);
  		
  		System.out.println(answer);
  	}
  	
  	static void dfs(int n, int tAnswer) {
  		if(n <= 2) {
  			if (answer < tAnswer) {
  				answer = tAnswer;
  			}
  		}
  		
  		int tempE = 0, tempIdx = 0, tempSum = 0;
  		for (int i = 1; i < n - 1; i++) {
  			tempE = energy.get(i);
  			tempIdx = i;
  			tempSum = energy.get(i-1) * energy.get(i+1);
  			energy.remove(tempIdx);
  			dfs(n-1, tAnswer + tempSum);
  			energy.add(tempIdx, tempE);
  		}
  	}
  }
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ16198 {
      
      private var N = 0
      private var weights: [Int] = []
      private var answer = -1
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          self.N = Int( readLine()! )!
          self.weights = readLine()!.split(separator: " ").map { Int($0)! }
      }
      
      private func calc() {
          addAndGetMoreScore(with: weights, 0)
      }
      
      private func addAndGetMoreScore(with array: [Int], _ totalScore: Int) {
          if array.count <= 2 {
              answer = max(answer, totalScore)
              return
          }
          
          for index in 1..<array.count - 1 {
              
              let score = array[index - 1] * array[index + 1]
              
              var temp = array
              temp.remove(at: index)
              
              addAndGetMoreScore(with: temp, score + totalScore)
          }
      }
      
      private func printAnswer() {
          print(answer)
      }
  }
  
  BJ16198().solve()
  

  • 시간,메모리