[백준] 5577 1학년 풀이

알고리즘

DP

풀이 과정

일단 생각나는 대로 짜봤다. 예상대로 시간초과가 난다. n이 최대 100이므로, 시간 복잡도가 2^100 이기 때문이다. 이를 dp로 메모이제이션 하는 작업이 필요할 것 같다.

   public static void dfs(int start, int end, int sum, int answer) {
        if (start == end) {
            if (sum == answer) {
                total++;
            }
            return;
        }
        int tempSum = sum + arr[start];
        if (0<= tempSum && tempSum <= 20) {
            dfs(start+1, end, tempSum, answer);
        }
        tempSum = sum - arr[start];
        if (0<= tempSum && tempSum <= 20) {
            dfs(start+1, end, tempSum, answer);
        }
    }

이를 DP로 다시 옮겨 주었다.

점화식을 구하는 과정은 어렵지 않았다. 다음과 같이 점화식을 세웠었다.

dp[i][j] = dp[i-1][j+arr[i-1]] + dp[i-1][j-arr[i-1]];

이는 i번째 숫자까지 봤을 때, j의 합을 가졌을 때의 경우의 수이다.

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

public class Main {

    public static StringTokenizer st = null;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
		public static int n;
    public static int[] arr;
    public static long[][] dp;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

처음에 DP의 basecode를 dp[1][arr[0]] = 1 가 아닌, dp[0][0] = 1 이라고 세웠었다. 그래서 한 82%센트 쯤에 틀렸었습니다 떴었는데 이유는 다음과 같다.

예시)

3

0 0 0

로 주어졌을 때,

dp[0][0] = 1이라면, dp[1][0] = 2, dp[2][0] = 4 가 되어 답은 4가 나온다.

하지만 우리가 예상한 답은, 0+0 = 0, 0-0= 0 으로 2이다.

최소한 +,- 가 하나쯤은 존재하려면, basecode가 0이 아닌 1에서 부터 시작하는 것으로 답을 매겨야 한다.

결론

DP를 풀면서 항상 느낀 것은 DP의 점화식을 올바르게 세웠는데 틀린 다면,for문의 범위를 제대로 잘 돌고 있는 지 그리고 basecode 초기화를 잘 시켜주고 있는지 따져야 한다.