문제 이해
숫자 배열에 들어있는 값으로 target 숫자 만들면 되는 문제
카테고리는 DFS/BFS로 되어있긴 한데, DP로 풀어도 될 듯 ??
오랜만에 DP로 풀어보겠다.
풀이
오랜만에 dp 알고리즘을 다루는 것이기 때문에 대략 이론적인 부분도 정리하겠음
일단 dp 문제를 풀 때 가장 중요하게 봐야할 건 아래 세 가지임
1. 상태를 무엇으로 표현할 것인가 ?
2. 이전 상태에세 다음 상태를 어떻게 만들 것인가 ?
3. 초기값은 무엇인가 ?이 문제 (숫자 몇 개를 사용해서 특정 합을 만들 수 있는 경우의 수)에서는 상태를
dp[i][sum]으로 볼 수 있다.
i는 몇 번째 숫자까지 사용했는지, sum은 현재까지 만들어진 합
예를 들면
dp[3][5] = 2
이거는 앞에서 3개의 숫자를 사용했을 때, 합이 5가 되는 방법이 두 가지 있다 라는 뜻임
이게 주관적으로 dp에서 가장 중요하다고 생각하는 상태 정의임
그리고 만약 다음 숫자가 추가로 더 있으면, 그 숫자로 인해 다음 합이 만들어질 것임
그럼 아래와 같이 표현할 수 있음
dp[3][5] -> dp[i][n]이렇게 현재 상태에서 다음 상태로 값을 전달하는데, 이걸 점화식이라고 함
dp에는 크게 두 가지 방식이 있음
1. Top-Down
탑다운은 재귀 + 메모이제이션을 사용하는 방식임
필요한 값을 재귀적으로 계산 -> 한 번 계산한 값은 배열에 저장 -> 다시 필요하면 저장된 값 사용이렇게 말로 정리해놓으니까 DFS랑 비슷하게 생긴 듯?
2. Bottom-Up
바텀업은 작은 상태부터 차례대로 채우는 방식
구글에 검색한 결과 “가장 작은 하위 문제부터 차례대로 답을 계산해 테이블을 채워나가는 방식” 이라고 함
보통 반복문을 사용
이 문제에서는 바텀업 방식이 적절해보인다.
그럼 일단 차근차근 생각을 해보자.
배열이 [1, 1, 1, 1, 1], target이 3이라고 가정해보자.
그렇다면 초기 상태를 어떻게 둘 것인가 ?
아무 숫자도 사용하지 않을 때의 합은 몇이고, 그 경우의 수는 몇 개인가 ?
아무 숫자도 사용하지 않을 때의 합은 0이고, 그 경우의 수는 1이다. (아무 것도 사용하지 않는 경우)
그럼 dp[0][0] = 1 로 볼 수 있음
다음 dp[1]은
0 + 1 = 1
0 - 1 = -1이기 때문에
dp[1][1] = 1
-> 숫자 한 개를 사용해서 합 1을 만드는 방법이 1개
dp[1][-1] = 1
-> 숫자 한 개를 사용해서 합 -1르 만드는 방법이 1개dp[2]는
1 + 1 = 2
1 - 1 = 0
-1 + 1 = 0
-1 - 1 = -2이기 때문에
dp[2][2] = 1
-> 숫자 두 개를 사용해서 합 2를 만드는 방법이 1개
dp[2][0] = 2
-> 숫자 두 개를 사용해서 합 0을 만드는 방법이 2개
dp[2][-2] = 1
-> 숫자 두 개를 사용해서 합 -2를 만드는 방법이 1개dp[3]은
2 + 1 = 3
2 - 1 = 1
0 + 1 = 1
0 - 1 = -1
0 + 1 = 1
0 - 1 = -1
-2 + 1 = -1
-2 - 1 = -3이기 때문에
dp[3][3] = 1
dp[3][1] = 3
dp[3][-1] = 3
dp[3][-3] = 1dp[4]
3 + 1 = 4
3 - 1 = -2
---
1 + 1 = 2
1 - 1 = 0
x3
---
-1 + 1 = 0
-1 - 1 = -2
x3
---
-3 + 1 = -2
-3 - 1 = -4dp[4][4] = 1
dp[4][2] = 3
dp[4][0] = 6
dp[4][-2] = 5
dp[4][-4] = 1dp[5]
4 + 1 = 5
4 - 1 = 3
---
2 + 1 = 3
2 - 1 = 1
x3
---
0 + 1 = 1
0 - 1 = -1
x6
---
-2 + 1 = -1
-2 - 1 = -3
x5
---
-4 + 1 = -3
-4 - 1 = -5dp[5][5] = 1
dp[5][3] = 4
dp[5][1] = 9
dp[5][-1] = 11
dp[5][-3] = 6
dp[5][-5] = 1이렇게 될 것임. 그럼 3이 나오는 경우는 총 5가지
노가다긴 했지만 이렇게 작성함으로써
서로 다른 경로가 같은 sum에 도착하면, 그 경우의 수를 dp에 합쳐 저장한다.
라는 걸 이해하기 위함이었다.
근데 위처럼 이차원 배열로 작성하면 sum에 음수가 올 수 있기 때문에 배열 인덱스로 사용할 수 없음
그래서 Map을 통해 key는 sum, value는 그 sum을 만드는 경우의 수가 오도록 작성하면 될 거 같음
코드
package programmers.P43165;
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
int[] n = {4, 1, 2, 1};
int t = 4;
System.out.println(solution(n, t));
}
public static int solution(int[] numbers, int target) {
Map<Integer, Integer> dp = new HashMap<>();
dp.put(0, 1);
for (int n : numbers) {
Map<Integer, Integer> next = new HashMap<>();
for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
int sum = entry.getKey();
int cnt = entry.getValue();
int plus = sum + n;
int minus = sum - n;
next.put(plus, next.getOrDefault(plus, 0) + cnt);
next.put(minus, next.getOrDefault(minus, 0) + cnt);
}
dp = next;
}
return dp.get(target);
}
}코드를 살펴보자면
일단 Map을 사용해서 dp를 구현했음
상태는 위에서 설명한대로 key는 sum, value는 sum을 만드는 경우의 수로 정의했음
그럼 아무 숫자도 사용하지 않은 최초 상태는 sum = 0, value = 1이 되어야 하기 때문에 0, 1 삽입
sum에 n을 더하거나 빼거나 두 가지 경우를 next라는 Map을 선언해서 삽입해준다
getOrDefault 메서드를 통해 같은 sum이 나오는 경우엔 경우의 수를 누적해줬음