백준 5557 JAVA : 1학년

문제

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

5557번: 1학년

 

풀이 예상

중간에 나오는 수가 0이상 20 이하이기 때문에 식을 이어 가면서 dp배열로 풀 수 있겠다고 생각했다.

 

지금 수를 기준으로, 이전수에 + 혹은 - 했을 때 의 개수를 증가시킨다.

ex) 이전 수가 8이고, 지금 수가 3인 경우 5와 11에 8의 개수만큼 증가시킨다.

 

마지막 수를 받고, dp[N-2][마지막 수]에 값이 올바른 등식의 개수이다.

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int num;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[][] dp = new long[N][21];
        num = Integer.parseInt(st.nextToken());
        dp[0][num] = 1;

        for (int i = 1; i < N-1; i++) {
            num = Integer.parseInt(st.nextToken());
            for (int j = 0; j <= 20; j++) {
                if(dp[i-1][j] > 0) { //이전에 숫자가 있었다면
                    if(0 <= j-num) {
                        dp[i][j-num] += dp[i-1][j];
                    }
                    if(j+num <= 20) {
                        dp[i][j+num] += dp[i-1][j];
                    }

                }
            }

        }
        num = Integer.parseInt(st.nextToken());
        System.out.println(dp[N-2][num]);

    }
}

 

결과