📌 Problem
0 이상 9 이하의 정수가 N개 주어진다. 처음 N - 1 개에 + 혹은 - 연산을 하여 N 번째 정수를 만들 수 있는 경우의 수를 반환하면 된다. 예를 들어 0 0 0 이 있으면 마지막 0을 만들 수 있는 방법은 0 - 0과 0 + 0으로 2가지이다. 다만, 연산의 과정 속에서 0 이상 20 이하의 숫자만이 나와야 한다. 예를 들어 0 1 ... 가 주어졌을 때 처음에 0 - 1은 음수가 되기 때문에 불가능한 연산이다.
📌 Example
예제를 통해 이해를 하는 것이 쉽기 때문에 예제 1번을 통해서 설명하고자 한다. 예제 1번은 총 10개의 숫자에 대한 연산을 통해 11번째 정수를 만들면 된다. 주어진 정수들은 row와 같으며 column은 연산 이후의 만들 수 있는 숫자의 개수이다.
첫 번째 정수 8을 통한 연산은 이전 값이 없기 때문에 바로 8만 1로 만든다.
8 다음 연산은 +3과 -3을 할 수 있다. 8만 1개 있기 때문에 5와 11을 1로 만든다.
세 번째 연산은 +2와 -2이다. 5와 11은 각각 3, 7, 9, 13이 될 수 있다.
마지막 정수 8은 연산 작업에 포함되지 않고 연산의 최종값이 된다. 때문에 직전 연산에 대해 8에 해당하는 개수를 구하면 된다. 표를 보면 마지막 연산에서 8을 만들 수 있는 경우의 수가 10이라는 것을 확인할 수 있다.
📌 Code
int N = Integer.parseInt(reader.readLine());
long[][] dp = new long[N - 1][21];
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
dp[0][Integer.parseInt(tokenizer.nextToken())]++;
for (int step = 1; step < dp.length; step++) {
int number = Integer.parseInt(tokenizer.nextToken());
for (int num = 0; num <= 20; num++) {
if (dp[step - 1][num] != 0) {
if (num - number >= 0) dp[step][num - number] += dp[step - 1][num];
if (num + number <= 20) dp[step][num + number] += dp[step - 1][num];
}
}
}
for (long[] longs : dp) {
System.out.println(Arrays.toString(longs));
}
result.append(dp[dp.length - 1][Integer.parseInt(tokenizer.nextToken())]);
Hello, Devs!