[백준 1126] 같은 탑

회고

• 어떤 값을 0번째부터 부터 하나씩 선택, 안선택 하는 문제는 DP 로 풀어야 함 (DFS)
• 하지만 N 이 50이므로, recursive call 을 하게되면 stack overflow 발생..
  • memoization 이 필요
• dp[사용한 조각 갯수][왼쪽 탑 높이][오른쪽 탑 높이] 이러면..
  • 50 * 500000 * 500000 헐
• dp[N][diff] 로 푼다
• dfs(n, diff) 아래 값 들 중 max
1. dp[n][diff] 또는 
2. dfs(n+1, diff)
3. difs(n, arr[n] + diff)
4. dfs(n , |diff - arr[n]|)

풀이

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

문제

홍준이는 N개의 직사각형 블록을 가지고 있다. 홍준이는 블록 위에 또다른 블록을 올려놓는 방식으로 탑을 만들 수 있다. 이때, 두 개의 탑을 만드는데, 이 두 탑의 높이가 같게 만드려고 한다. (각 탑은 적어도 한 개의 블록을 포함해야 한다) 홍준이는 되도록이면 탑의 높이를 최대로 하려고 한다. 그리고 모든 블록을 사용할 필요는 없다.

각 블록의 높이가 주어질 때, 홍준이가 만들 수 있는 탑의 높이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘지 않는다.

출력

첫째 줄에 문제의 정답을 출력한다. 불가능할 때는 -1을 출력한다.

소스

import java.util.Arrays; import java.util.Scanner; public class Main { public static int N; public static int[][] dp; public static int[] arr; public static int inf = 1 << 20; public static int search(int n, int diff) { if (diff > 250000) return -inf; if (N == n) { if (diff == 0) return 0; else return -inf; } if (dp[n][diff] != -1) return dp[n][diff]; // 아무 선택하지 않은 경우 dp[n][diff] = search(n + 1, diff); // 차이를 더 벌리는 경우 dp[n][diff] = Math.max(dp[n][diff], search(n + 1, diff + arr[n])); // 차이를 좁히는 경우 if (arr[n] > diff) { dp[n][diff] = Math.max(dp[n][diff], diff + search(n + 1, arr[n] - diff)); } else { dp[n][diff] = Math.max(dp[n][diff], arr[n] + search(n + 1, diff - arr[n])); } return dp[n][diff]; } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dp = new int[N + 1][250001]; arr = new int[N + 1]; for (int i = 0; i < N; i++) { arr[i] = sc.nextInt(); Arrays.fill(dp[i], -1); } int ans = search(0, 0); System.out.println(ans > 0 ? ans : -1); sc.close(); } }