5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀
www.acmicpc.net
조합과 dp를 이용하여 해결하였습니다.
0 ~ N - 2를 조합하여 N - 1번째 값이 나오는 갯수를 출력하는 문제입니다.
단, 더하거나 빼는 과정에서 음수나 20보다 커지면 안됩니다.
저는 배열을 dp[idx][now] => (현재 idx에서 값이 now일 경우의 수)
0번 인덱스의 값은 무조건 +로 들어가니 그 다음인 1번 인덱스와, list[0]으로 재귀를 돌려줍니다.
now + list[idx] <= 20 일 경우에만 더한 값을 다음으로 넘겨주고
now - list[idx]>=0 일 경우에만 뺀 값을 다음으로 넘겨줍니다.
인덱스가 N - 1이 되면 지금까지 구한 값이 list[N - 1]와 같은지 확인하고 값을 리턴시켜줍니다.
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static long dp[][];
static int N, list[];
static long func(int idx, int now) {
if (idx == N - 1) {
if (now == list[idx])
return dp[idx][now] = 1;
return dp[idx][now] = 0;
}
if (dp[idx][now] != -1)
return dp[idx][now];
dp[idx][now] = 0;
if (now + list[idx] <= 20)
dp[idx][now] += func(idx + 1, now + list[idx]);
if (now - list[idx] >= 0)
dp[idx][now] += func(idx + 1, now - list[idx]);
return dp[idx][now];
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N];
dp = new long[N][21];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
}
static void init() {
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
}
}
public static void main(String[] args) throws Exception {
input();
init();
System.out.println(func(1, list[0]));
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 5569 출근 경로 (0) | 2021.02.06 |
|---|---|
| boj 1010 다리 놓기 (0) | 2021.02.05 |
| boj 5573 산책 (0) | 2021.02.04 |
| boj 17528 Two Machines (0) | 2021.01.28 |
| boj 9657 돌 게임 3 (0) | 2021.01.27 |