boj 5557 1학년

www.acmicpc.net/problem/5557

5557번: 1학년

조합과 dp를 이용하여 해결하였습니다.

 

0 ~ N - 2를 조합하여 N - 1번째 값이 나오는 갯수를 출력하는 문제입니다.

단, 더하거나 빼는 과정에서 음수나 20보다 커지면 안됩니다.

저는 배열을 dp[idx][now] => (현재 idx에서 값이 now일 경우의 수)

 

0번 인덱스의 값은 무조건 +로 들어가니 그 다음인 1번 인덱스와, list[0]으로 재귀를 돌려줍니다.

now + list[idx] <= 20 일 경우에만 더한 값을 다음으로 넘겨주고

now - list[idx]>=0 일 경우에만 뺀 값을 다음으로 넘겨줍니다.

 

인덱스가 N - 1이 되면 지금까지 구한 값이 list[N - 1]와 같은지 확인하고 값을 리턴시켜줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static long dp[][];
    static int N, list[];
 
    static long func(int idx, int now) {
        if (idx == N - 1) {
            if (now == list[idx])
                return dp[idx][now] = 1;
            return dp[idx][now] = 0;
        }
 
        if (dp[idx][now] != -1)
            return dp[idx][now];
 
        dp[idx][now] = 0;
 
        if (now + list[idx] <= 20)
            dp[idx][now] += func(idx + 1, now + list[idx]);
 
        if (now - list[idx] >= 0)
            dp[idx][now] += func(idx + 1, now - list[idx]);
 
        return dp[idx][now];
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        dp = new long[N][21];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        init();
        System.out.println(func(1, list[0]));
    }
}