[Java] 백준 5557번 1학년

다이나믹 프로그래밍 문제입니다.

수열이 주어지고 수열사이에 +, -를 넣어서 마지막으로 주어진 값을 만들면 됩니다.
가능한 경우의 수를 출력해주어야 합니다.

* 계산하는 중간에 0보다 작거나 20보다 큰 경우가 생기면 계산하지 않습니다.

첫번째 값을 해당하는 위치에 넣습니다.
두번째~N-1번째는 (배열에 값 + 현재값), (배열에 값 - 현재값)의 위치에 배열에 값을 더해줍니다.

index = j + num;
if (index <= 20) {
  next[index] += arr[j];
}

index = j - num;
if (index >= 0) {
  next[index] += arr[j];
}

전부 더해주었다면 현재 배열을 더해준 배열로 변경합니다.

for (int j = 0; j <= 20; ++j) {
    arr[j] = next[j];
    next[j] = 0;
}

위의 과정을 반복하여 배열[마지막값] 의 값을 출력해주었습니다.

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

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

    int n = Integer.parseInt(st.nextToken());
    long[] arr = new long[21];
    long[] next = new long[21];
    long result = 0;

    st = new StringTokenizer(br.readLine());
    int num = Integer.parseInt(st.nextToken());
    arr[num] = 1;

    for (int i = 1; i < n - 1; ++i) {
      int index;
      num = Integer.parseInt(st.nextToken());

      for (int j = 0; j <= 20; ++j) {
        if (arr[j] == 0) {
          continue;
        }

        index = j + num;
        if (index <= 20) {
          next[index] += arr[j];
        }

        index = j - num;
        if (index >= 0) {
          next[index] += arr[j];
        }
      }

      for (int j = 0; j <= 20; ++j) {
        arr[j] = next[j];
        next[j] = 0;
      }
    }

    int resultIndex = Integer.parseInt(st.nextToken());
    bw.write(arr[resultIndex] + "\n");
    bw.close();
  }
}