[백준문제풀이] 5557 1학년 java

 

접근법 : 

**1) 어떻게 풀 것인가?**

 

내가 생각한것 

1. int[] ints 에 n개의 수를 입력받는다. 

2. idx대로 한칸씩 나아가며 +,-를 한다. 

3. 이때 계산한 수가 20 초과 or 0미만이라면 다음 계산으로 넘어간다. 

4. 0~ n-2번째 idx까지 계산한 값중 n-1 idx의 값이 같은것의 개수를 센다.

 

이 문제는 어떤식으로 풀어야할지 순서는 짤 수 있는데 저 '다음 계산으로 넘어간다' 와 ' n-2까지 계산한 값' 을 어디에 저장해야할지 아이디어가 떠오르지 않았다. 

dp저장을 어떻게 해야할지에 대해서 고민이었다. 

그래서 다른 블로그의 힘을 빌려... 코드를 쓰게 되었다. 

 

**2) 시간복잡도**

O(n)의 시간복잡도를 가진다.

 

**3) 공간복잡도**

128mb이다.

 

**4) 풀면서 놓쳤던점**

dp!!!!! dp는 왜이리 어려운거야

 

**5) 이 문제를 통해 얻어갈 것**

dp에 대한 감..

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];
        String[] strings = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(strings[i]);
        }

        // dp[i][j]: i번째 숫자까지 사용하여 합이 j인 등식의 개수
        long[][] dp = new long[N - 1][21];

        // 초기값 설정
        dp[0][numbers[0]] = 1;

        // 동적 프로그래밍
        for (int i = 1; i < N - 1; i++) {
            for (int j = 0; j <= 20; j++) {
                if (dp[i - 1][j] > 0) {
                    int nextSum1 = j + numbers[i];
                    int nextSum2 = j - numbers[i];
                    if (nextSum1 >= 0 && nextSum1 <= 20) {
                        dp[i][nextSum1] += dp[i - 1][j];
                    }
                    if (nextSum2 >= 0 && nextSum2 <= 20) {
                        dp[i][nextSum2] += dp[i - 1][j];

                    }
                }
            }
        }

        // 마지막 등식의 결과가 마지막 숫자와 같은 경우를 세어 결과 출력
        long answer = dp[N - 2][numbers[N - 1]];
        System.out.println(answer);
    }
}