[BOJ] 백준 5557 - 1학년

백준 5557 - 1학년

---

상근이는 덧셈, 뺄셈을 통해 줄 지어진 숫자를 연산하여 가장 마지막 숫자가 나오도록 하고자 한다.

그러나, 연산 도중에 나올 수 있는 숫자는 0이상 20이하라고 한다.

 여기서 크기가 21인 배열을 생각할 수 있다.

예시인 "8 3 2 4 8 7 2 4 0 8 8" 을 생각해보자.

처음 8이 올 때, 8이 될 수 있는 경우의 수는 1이다.

8 다음 3이 올 때, 3에서 할 수 있는 연산은 +3, -3 이다.

그 다음 2가 올 때 할 수 있는 연산은 +2, -2 이다.

4가 올 때 할 수 있는 연산은 +4, -4 로 범위를 넘어가면 빼주면 된다.

위의 방식을 코드에 적용하면 다음과 같다.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
    
        long[] num = null;
        for(int i=0; i<n-2; i++) {
            if(i==0) {
                num = new long[21];
                num[arr[0]] = 1;
            }
            num = calSum(arr, num, i+1);
        }
        
        System.out.println(num[arr[n-1]]);
        
        sc.close();
    }
 
    private static long[] calSum(int[] arr, long[] tmp, int x) {
        
        long[] num  = new long[21];
        for(int i=0; i<21; i++) {
            if(tmp[i] == 0) continue;
            else {
                if(i-arr[x] >= 0 && i-arr[x] <= 20) {
                    num[i-arr[x]] += tmp[i];
                }
                if(i+arr[x] >= 0 && i+arr[x] <= 20) {
                    num[i+arr[x]] += tmp[i];
                }
            }
        }
        return num;
        
    }
 
 
}