[Java] 백준 16198번 : 에너지 모으기

1. 문제

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

 

 

2. 풀이과정

[방법 1] DFS + 새로운 배열 선언 방식

새로운 배열을 만들어서 DFS를 구현했다. 메모리는 많이 사용하지만, 메서드가 종료될 때 배열을 원상태로 되돌리지 않아도 돼서 빠르다.

마지막에 요소가 2개 남았을 때, 최대값을 업데이트해주고 종료한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        solve(arr, N, 0);
        System.out.println(result);

    }

    public static void solve(int[] arr, int size, int energy){
        if(size == 2){
            result = Math.max(result, energy);
            return;
        }

        for(int i=1; i<size-1; i++){
            int[] newArr =  new int[size - 1];
            int idx = 0;
            for(int j=0; j<i; j++){
                newArr[idx++] = arr[j];
            }

            for(int j=i+1; j<size; j++){
                newArr[idx++] = arr[j];
            }
            solve(newArr, size - 1, energy + (arr[i-1] * arr[i+1]));
        }

    }
}

 

결과

 

 

[방법 2] DFS + Indexing

각 노드마다 자신의 앞을 가르키는 index와 뒤를 가르키는 index 그리고 자신의 값을 가지도록 한다.

이 방법은 Double LinkedList구조와 유사하다고 할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int result;
    static Node[] nodes;

    static class Node{
        int prevIdx, val, nextIdx;

        public Node(int prevIdx, int val, int nextIdx){
            this.prevIdx = prevIdx;
            this.val = val;
            this.nextIdx = nextIdx;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodes = new Node[N];
        for(int i=0; i<N; i++){
            nodes[i] = new Node(i-1, Integer.parseInt(st.nextToken()), i+1);
        }
        solve(N-2, 0);
        System.out.println(result);

    }

    public static void solve(int size, int energy){
        if(size == 0){
            result = Math.max(result, energy);
            return;
        }

        int idx = nodes[0].nextIdx;//배열 시작 인덱스값
        for(int i=0; i<size; i++){
            nodes[nodes[idx].prevIdx].nextIdx = nodes[idx].nextIdx;
            nodes[nodes[idx].nextIdx].prevIdx = nodes[idx].prevIdx;
            solve(size - 1, energy + nodes[nodes[idx].prevIdx].val * nodes[nodes[idx].nextIdx].val);
            nodes[nodes[idx].prevIdx].nextIdx = idx;
            nodes[nodes[idx].nextIdx].prevIdx = idx;
            idx = nodes[idx].nextIdx;
        }

    }
}

 

결과