[백준] 16198. 에너지 모으기 (Java)

 

16198번: 에너지 모으기

풀이

• 배열로 수를 저장하고 선택한 수에 대해선 visited = false로 처리하여 백트래킹으로 진행한다.

 

 

시행착오

• 처음에 백트래킹 수행하는 method의 인자를 고른 수로 했다.
• 이렇게 되면 left, right가 linear하게 선택되서 답이 제대로 안나왔다.
• for문 안에 넣어야 하는데 어떻게 바꿀지 모르겠어서 결국 솔루션을 참고했다.
  • method의 인자는 n과 m 문제처럼 depth를 인자로 넣고, depth가 N-2가 되었을 때 max값인지 아닌지 판단하고 return하면 된다.
  • 에너지 합은 우선 left, right를 for문의 인자 i를 기준으로 찾고, (sum + left * right)를 인자로 넘겨주면 된다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static long ans;
    static int[] arr;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visited = new boolean[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        solve(0, 0);

        bw.write(String.valueOf(ans));
        br.close();
        bw.close();
    }

    // for문 안에 left, right 찾기를 해야함
    // 백트래킹 form으로 가기
    public static void solve(int cnt, long sum) {
        if (cnt == N - 2) {
            ans = Math.max(sum, ans);
            return;
        }

        for (int i = 1; i < N-1; i++) {
            if (visited[i]) continue;

            int left = i, right = i;
            while(left-- > 0) {
                if (!visited[left]) break;
            }

            while(right++ < N - 1) {
                if (!visited[right]) break;
            }

            visited[i] = true;
            solve(cnt + 1, sum + (arr[left] * arr[right]));
            visited[i] = false;
        }
    }
}