[백준] code.plus(브루트포스 - 재귀,JAVA)16198번, 에너지 모으기

문제 링크

16198번: 에너지 모으기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 첫 번째와 마지막 구슬은 선택할 수 없다.

2. 선택한 구슬의 양 옆의 구슬의 무게의 곱만큼 에너지를 얻는다.

3. 구할 수 있는 에너지의 최대 양을 결과로 출력해야 한다.

 

 

재귀를 이용하여 간단하게 구현하였습니다.

 

재귀의 순서는

1. 현재 놓은 구슬 중 첫 번째와 마지막 구슬을 제외한 구슬을 선택합니다.

2. 해당 구슬의 양 옆의 구슬에 대한 에너지를 구합니다.

3. 선택한 구슬을 제거합니다.

4. 제거한 구슬에 경우를 재귀를 통해 이후에 경우도 탐색합니다.

5. 제거한 구슬을 다시 추가한 뒤 1번을 다시 진행합니다.

 

모든 재귀가 끝난 뒤 최대 에너지를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 구슬에 대한 무게를 저장하였습니다.
• 최대 에너지를 얻는 cal 함수를 실행하였습니다.
• 최대 에너지를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 재귀를 통해 구슬을 선택하는 모든 경우의 수에서 최대 에너지를 구합니다.

 

import java.io.*;
import java.util.*;
public class Main {
	static ArrayList<Integer> marble = new ArrayList<>();	//구슬 무게 저장 리스트
	static int N,result = -1;
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	N = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력되는 구슬 무게 저장
    	for(int i=0;i<N;i++)
    		marble.add(Integer.parseInt(st.nextToken()));
    	cal(0);		//최대 에너지 구하는 함수 실행
    	bw.write(result + "\n");		//최대 에너지 BufferedWriter 저장
    	bw.flush();		//결과출력
    	bw.close();
    	br.close();
    }
    //최대 에너지 구하는 재귀 함수
    static void cal(int cur) {
    	int size = marble.size();
    	if(size==2) {		//구슬이 2개 남았을 때
    		result = Math.max(result, cur);
    		return;
    	}
        //첫 번째, 마지막 구슬 제외 구슬 선택하기
    	for(int i=1;i<size-1;i++) {
    		int temp = marble.get(i);
    		int w = marble.get(i-1) * marble.get(i+1);
    		marble.remove(i);
    		cal(cur + w);
    		marble.add(i,temp);
    	}
    	return;
    }
}