https://www.acmicpc.net/problem/5557
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
풀이
N은 최대 100이므로, 모든 경우를 탐색하는 브루트포스 풀이는 시간초과가 발생합니다. 따라서, 다른 알고리즘을 생각해봐야 합니다... 생각을 하다보면,
(i번째 원소까지의 합이 sum이 되는 경우의 수) = (i-1번째 원소까지의 합이 sum - i번째 원소가 되는 경우의 수) + (i-1번째 원소까지의 합이 sum + i번째 원소가 되는 경우의 수)임을 알 수 있습니다. 다만 문제 조건에 따라서, 0 이상 20 이하이여야 할 것입니다.
원래 저는 바텀업 풀이를 좋아하나(직관적입니다~), 왠지 모르게 이번 문제에서는 탑다운 풀이 방법이 떠올랐습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.io.*;
import java.util.*;
public class Main {
static int[] nums;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
nums = new int[N-1];
dp = new long[N-1][21];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N-1; i++) {
nums[i] = Integer.parseInt(st.nextToken());
if (i > 0) Arrays.fill(dp[i], -1); // 방문처리를 위해 -1로 초기화
}
int target = Integer.parseInt(st.nextToken());
dp[0][nums[0]] = 1;
System.out.println(dfs(N-2, target));
}
static long dfs(int i, int sum) {
if (i == 0) return dp[i][sum];
if (dp[i][sum] > -1) return dp[i][sum];
long ret = 0;
if (sum + nums[i] <= 20) ret += dfs(i-1, sum + nums[i]);
if (sum - nums[i] >= 0) ret += dfs(i-1, sum - nums[i]);
return dp[i][sum] = ret;
}
}
|
cs |