문제
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
관찰
-
숫자들이 주어지고, 더하기와 빼기만을 이용한다.
-
숫자의 개수 2 ≤ numbers.length ≤ 20, number는 50 이하의 자연수
-
target 은 1000이하의 자연수
-
dfs를 사용한다면?
- 점화식의 수행은 더하기와 빼기
- 종료 조건은 numbers의 수를 모두 사용한 상태
depth==numbers.lenth- 경우의 수를 찾는 중이므로, 종료 조건에 도달한 시점에 수식의 결과가
target일 경우를 count한다.
-
dp를 사용한다면?
20 * 50 = 1000이므로 numbers에서 발생할 수 있는 수는 -1000~1000 즉 2001개의 경우의 수 밖에 없다.
알고리즘
기본적인 DFS 문제이지만, BFS나 DP로도 풀어볼 수 있다.
풀이
BFS 풀이
import java.util.*;
class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
for (int i = 0; i < numbers.length; i++) {
int size = queue.size();
for (int j = 0; j < size; j++) {
int sum = queue.poll();
queue.add(sum + numbers[i]);
queue.add(sum - numbers[i]);
}
}
while (!queue.isEmpty()) {
if (queue.poll() == target) {
answer++;
}
}
return answer;
}
}DFS 풀이
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(0, numbers, target, 0);
return answer;
}
private void dfs(int depth, int[] numbers, int target, int sum) {
if (depth == numbers.length) {
if (sum == target) {
answer++;
}
return;
}
dfs(depth + 1, numbers, target, sum + numbers[depth]);
dfs(depth + 1, numbers, target, sum - numbers[depth]);
}
}DFS 풀이 2
- numbers 배열의 길이와 depth가 같으면 sum이 target과 같은지 확인하고 같으면 1, 아니면 0을 반환한다.
- numbers 배열의 길이와 depth가 같지 않으면 dfs를 호출하여 sum에 numbers[depth]를 더한 값과 뺀 값을 각각 넣어준다.
- dfs를 호출한 결과를 더하여 반환한다.
class Solution {
public int solution(int[] numbers, int target) {
return dfs(0, numbers, target, 0);
}
private int dfs(int depth, int[] numbers, int target, int sum) {
if (depth == numbers.length) {
if (sum == target) {
return 1;
}
return 0;
}
return dfs(depth + 1, numbers, target, sum + numbers[depth]) + dfs(depth + 1, numbers, target, sum - numbers[depth]);
}
}DP 풀이
코드 설명
- numbers 배열의 길이를 n이라고 하고, dp 배열을 2001 크기로 선언한다.
- dp 배열의 인덱스는 -1000부터 1000까지이다. 따라서 dp[1000]은 0이 아닌 1로 초기화한다.
- numbers 배열의 길이만큼 반복문을 돌면서, 다음과 같은 과정을 반복한다.
- nextDp 배열을 2001 크기로 선언한다.
- dp 배열의 인덱스를 0부터 2000까지 반복하면서, dp[j]가 0이 아닌 경우에만 다음과 같은 과정을 반복한다.
- nextDp[j + numbers[i - 1]]에 dp[j]를 더한다.
- nextDp[j - numbers[i - 1]]에 dp[j]를 더한다.
- dp 배열을 nextDp 배열로 바꾼다.
- dp[target + 1000]을 리턴한다.
class Solution {
public int solution(int[] numbers, int target) {
int n = numbers.length;
int[] dp = new int[2001];
dp[1000] = 1;
for (int i = 1; i <= n; i++) {
int[] nextDp = new int[2001];
for (int j = 0; j <= 2000; j++) {
if (dp[j] != 0) {
nextDp[j + numbers[i - 1]] += dp[j];
nextDp[j - numbers[i - 1]] += dp[j];
}
}
dp = nextDp;
}
for (int i = 900; i < 1100; i++) {
System.out.println(i + " " + dp[i]);
}
return dp[target + 1000];
}
}