[BOJ 5557] 1학년 (Java, DP)

 

---

문제 링크 

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

5557번: 1학년

---

문제 풀이 

- 입력의 경우 int 배열로 100개까지 받으므로 400byte

- 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음

- 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리

 

시간 복잡도

상향식 (Bottom-Up)	하향식(Top-Down, 재귀 함수)
O(N * 20)	O(2^n) = O(2^100)

- 재귀 함수를 사용하는 Top-Down의 경우 DP Memorization 기법 사용하여 풀이 해야 시간초과 발생하지 않음

---

제출 코드 

Bottom-Up 방식

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int N;
    static int[] DATA;
    static long[][] DP;

    public static void main(String[] args) throws IOException {
        input();

        pro();

        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();

        DATA = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            DATA[i] = inputProcessor.nextInt();
        }

        DP = new long[N + 1][21];
        DP[1][DATA[1]] = 1;
    }

    private static void pro() {
        bottomUp();
    }

    private static void bottomUp() {
       for(int i = 2; i < N; i++) {
           for(int j = 0; j <= 20; j++) {
               if(DP[i - 1][j] > 0) {
                   int v1 = j + DATA[i];
                   int v2 = j - DATA[i];

                   if(isValid(v1)) DP[i][v1] += DP[i - 1][j];

                   if(isValid(v2)) DP[i][v2] += DP[i - 1][j];
               }
           }
       }

       sb.append(DP[N - 1][DATA[N]]); // DATA[N]과 동일한 값이 몇 개 있는지 
    }

    private static boolean isValid(int value) {
        return 0 <= value && value <= 20;
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}

 

Top-Down 방식

- tree에서 leaf node 구하는 문제와 유사

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

public class Main {
    static int N;

    static int[] DATA;

    static long[][] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        DATA = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            DATA[i] = Integer.parseInt(st.nextToken());
        }

        DP = new long[21][101]; // sum, depth
        for(long[] d : DP) Arrays.fill(d, -1);
    }

    static long rec(int sum, int depth) {
        if(sum < 0 || sum > 20) return 0L;
        if(depth == N - 1) {
            return sum == DATA[N] ? 1L : 0L;
        }

        if(DP[sum][depth] != -1) return DP[sum][depth];

        return DP[sum][depth] = rec(sum + DATA[depth + 1], depth + 1) + rec(sum - DATA[depth + 1], depth + 1);
    }

    static void pro() {
        System.out.println(rec(DATA[1], 1));
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}