접근
처음엔 기존 냅색 알고리즘(평범한 배낭 문제)처럼 이차원 dp 배열을 선언했었다. dp[i][j] = i번째 동전까지 써서 j원을 만들 수 있는 경우의 수로 정의하고. 그런데 문제를 다시 생각해보니, 서로 다른 물건을 담는 것과는 다르게 이 문제에서는 같은 금액의 동전을 여러 번 써도 된다는 점을 깨달았다. 그래서 for(int i = 0;i < m;i += coin) 과 같이 n개의 동전에 대해서 모두 1을 설정한 후 시작해야 하나? 싶었다. 근데 그러면 배열에 0이 너무 많고 비효율적인 것 같아서 접근이 잘못된 것 같았다.
그래서 사실 솔루션을 살짝 참고했다.. 역시나 이차원이나 쓸 필요가 없었다. 2년 만에 알고리즘을 풀다보니 까먹은 내용이 너무 많았는데, 특히 dp가 감을 다시 되살리기 제일 어려운 것 같다. 앞으로는 일차원 배열을 재사용할 수 있는지 고려해볼 것! 그리고 무엇보다 dp는 직접 표를 그려가며 규칙을 찾는게 제일 쉬운 접근법인 것 같다. 머리로만 풀려고 하지 말자.
코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int t = 0;t < tc;t++){
// 입력값 저장
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] coins = new int[n];
for(int i = 0;i < n;i++){
int coin = Integer.parseInt(st.nextToken());
coins[i] = coin;
}
int m = Integer.parseInt(br.readLine());
// 냅색 알고리즘 계산
int answer = solve(coins, n, m);
sb.append(answer).append("\n");
}
// 결과값 출력
System.out.println(sb.toString());
}
static int solve(int[] coins, int n, int m){
int result = 0;
int[] dp = new int[m+1];
for(int i = 1;i <= n;i++){
int curCoin = coins[i-1];
for(int j = 0;j <= m;j++){
if(j == curCoin) dp[j] += 1;
else if(curCoin < j) dp[j] += dp[j-curCoin];
}
}
result = dp[m];
return result;
}
}
'Algorithm' 카테고리의 다른 글
[백준] 1976: 여행 가자 JAVA (0) | 2025.03.01 |
---|---|
[백준] 11403: 경로 찾기 JAVA (0) | 2025.02.28 |
[백준] 12865: 평범한 배낭 JAVA (0) | 2025.02.13 |
[백준] 13904: 과제 JAVA (0) | 2023.03.20 |
[백준] 1374: 강의실 JAVA (0) | 2023.03.20 |