알고리즘 분류 (dp)
https://www.acmicpc.net/problem/2293
# 문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
# 예제
입력 : 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
3 10
1
2
5
출력 : 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
10
# 필요개념
n이 100 이하, k가 10000 이하이고, 시간 제한이 0.5초이기 때문에, 코드를 짤 때 O(nk) 선에서 끝내야했다. 이 점을 유의하고 코드를 짜기 시작했는데,
틀린 풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] coin = new int[n];
int[][] dp = new int[k + 1][n + 1];
dp[0][0] = 1;
for (int i = 0 ; i < n ; i++) {
coin[i] = Integer.parseInt(br.readLine());
dp[0][i + 1] = 1;
}
Arrays.sort(coin);
for (int j = 1 ; j <= n ; j++) {
int obj = coin[j - 1];
for (int i = 1 ; i <= k ; i++) {
for (int o = 0 ; o <= i / obj ; o++) { // obj의 개수
dp[i][j] += dp[i - (o * obj)][j - 1];
}
}
}
System.out.println(dp[k][n]);
}
}
3초에서 시간초과가 발생한 코드이다. dp로 풀기 위해 (k + 1) * (n + 1) 크기의 이차원 배열을 선언했다. coin 배열을 오름차순으로 정렬해두고, 크기가 작은 동전의 경우의 수를 이차원 배열에 채워나갔다.
해당 문제의 예제에서
coin = 1인 경우 k가 1일때부터 10일때까지 모든 경우에서 k % coin == 0 을 만족한다. 이럴 때마다 dp[0][coin - 1]을 더해나갔다.
그런데 만약 k가 10이고 coin이 5인 경우에는
5가 들어가는 개수가 0, 1, 2로 나뉘게 되기 때문에 for문을 한 개 더 쓸 수밖에 없었다. 시간초과가 날 걸 예상했지만 역시나 정말 나버렸다. 그래서 고민하다가 2차원 배열이 아닌 1차원 배열을 만든 후, 그 위에 누적하는 방법을 선택했다.
정답 풀이
틀린 풀이와의 차이점은 dp[0][1] + dp[1][1] + dp[2][1] => dp[1] 로 합쳐졌다는거! 생각해보니 dp[all][coin - 1] 로 지정할 거라면, 굳이 이차원 배열로 만들 필요 없이 그 위에 누적하면 되는 것이었다
초반에 생각한대로 O(nk) 선에서 끝낼 수 있었다!
# Code
import java.io.*;
import java.util.*;
// 2293
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[] coin = new int[n + 1];
int[] dp = new int[k + 1];
dp[0] = 1;
for (int i = 0 ; i < n ; i++) {
coin[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(coin);
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= k ; j++) {
if (coin[i] > j) continue;
dp[j] += dp[j - coin[i]];
}
}
System.out.println(dp[k]);
}
}
# 결과
'코딩테스트 > 백준 골드' 카테고리의 다른 글
[백준] 1092: 배 (그리디 알고리즘, 정렬) - JAVA (0) | 2025.01.06 |
---|---|
[백준] 7453: 합이 0인 네 정수 (이분탐색, upper bound & lower bound) - JAVA (0) | 2024.12.28 |
[백준] 11404: 플로이드 (플로이드-워셜 알고리즘) - JAVA (0) | 2024.12.23 |
[백준] 9527 : 1의 개수 세기 (DP, 비트마스킹, 누적합) - JAVA (0) | 2024.11.21 |
[백준] 17404: RGB거리 2 (DP) - JAVA (0) | 2024.11.13 |