[자바] 백준 5557 - 1학년 (java)

 문제 : boj5557

---

 

필요 알고리즘 개념

• 동적 계획법 (DP; Dynamic Programming)
  
  • DP를 이용한 문제이다. DP 개념을 적용해서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  약간 응용되었지만, 아무튼 기본형태의 DP문제이다. 참고로 '경우의 수' 어쩌구 하는 문제의 대부분은 DP로 해결된다. 우선 단순히 +, -를 넣어서 모든 경우를 보려면 O((N-2)^2)이 필요하므로 시간초과가 나게 된다.

 

  이 문제가 그래도 쉬운점은, 계산 중간에 음수가 없고 계산 중간의 모든 값이 [0, 20] 이내라는게 보장된다는 점이다. 그렇다면 매번 +, - 기호를 넣어보면서 0부터 20까지 각각 만들 수 있는 경우의 수를 세보면 된다.

 

  dp[a][b]를 a번째 수를 +나 -로 넣어서 b를 만들 수 있는 경우의 수로 정의하자. 입력으로 주어진 N개의 수를 Ai 라고 하자(0<=i<n-1).

그럼 초기값은 dp[0][A0] = 1 이 될 것 이다. 이후 A1 수를 가지고 0~20을 만들 수 있는 경우의 수를 생각해보자.

0은 만들 수 없다. 1도 만들 수 없다.... 5는 8-3=5 이므로 만들 수 있다. 6은 만들 수 없다... 11은 8+3=11이므로 만들 수 있다. 12는 만들 수 없다.... 20은 만들 수 없다.

일반화 해보면, num을 0부터 20까지 보면서, i 인덱스는 dp[i][num] = dp[i-1][num-Ai] + dp[i-1][num+Ai] 라고 볼 수 있다. 이 때, num-Ai가 0 미만이거나, num+Ai가 20초과인 경우는 제외시켜야 한다.

 

  예시로 예제 입력 1에 대해 dp를 그려보면 다음과 같다.(이하 그림은 dp[a][b]를 그리려니 너무 너비가 커져서 dp[b][a]로 그린 것이다. 즉 가로가 n번째 수가 되고, 세로가 num에 해당한다.) 화살표는 다 그리려니 너무 지저분해서 중간까지만 그렸다. 이해하는덴 문제 없을 거라 생각된다.

 

  최종적으로 dp[n-2][마지막 수]이 답이 된다(빨간 네모 부분). 왜냐면 마지막 수에 대해 '=8' 처럼 수식의 끝을 지어야 하기 때문이다.

 

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());

        long[][] dp = new long[n-1][21];
        dp[0][arr[0]] = 1;
        for (int i = 1; i < n-1; i++) {
            for (int num = 0; num <= 20; num++) {
                if (num-arr[i] >= 0)    dp[i][num]+=dp[i-1][num-arr[i]];
                if (num+arr[i] <= 20)   dp[i][num]+=dp[i-1][num+arr[i]];
            }
        }
        System.out.println(dp[n-2][arr[n-1]]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}