[백준/JAVA] 2293 - 동전 1

문제 정보

https://www.acmicpc.net/problem/2293

 

문제

 

문제 해결 과정

완전 탐색으로 풀이

서로 다른 n가지 동전을 사용하는 경우의 수는 다음과 같다.

동전 1(사용/미사용 → 2개) x 동전 2(사용/미사용 → 2개) x ... x 동전 n(사용/미사용 → 2개) = 2^n개

 

문제조건에서 n이 최대 100이라고 하였으므로, 2^100 ≒ 10^30이므로, 문제 제한인 1초를 많이 초과한다. (사실은 하나의 동전을 무한 번 사용 가능하므로, 실제로는 이보다 경우의 수가 많을 것이다.)

따라서, 서로 다른 n가지 동전을 사용하는 모든 경우의 수에 대해 이 금액이 k원인지 확인하는 방식은 적합하지 않다.

 

DP 풀이

DP[ i ][ j ]를 1, 2, ... i번째까지 동전을 고려해서, j원을 만드는 경우의 수라고 하자.

 

설명	DP[0][0]	DP[0][1]	...	DP[0][k]
1번째 동전 고려	DP[1][0]	DP[1][1]	...	DP[1][k]
1~2번째 동전 고려	DP[2][0]	DP[2][1]	...	DP[2][k]
	...
1~n번째 동전 고려	DP[n][0]	DP[n][1]	...	DP[n][k]

 

이전까지 동전을 고려한 경우에 현재 새로운 동전을 추가했을 때의 경우의 수를 구하면 된다.

또한 현재 새로운 동전을 추가했을 때는 해당 동전을 사용하는 경우, 사용하지 않는 경우가 있을 수 있다.

DP[x][j] = DP[x - 1][j] + DP[x][j - x번째 동전의 금액]
여기서, DP[x-1][j]는 추가된 동전을 사용 x, DP[x][j - x번째 동전의 금액 ]는 추가된 동전을 사용 o

 

DP 풀이의 시간복잡도

위의 2차원 배열 채워나가는 시간이므로, 대략 n * k = 100 * 10,000 = 10^6이므로, 문제 제한인 1초에 충분하다.

 

DP 풀이의 공간복잡도

int로 2차원 배열을 만든다면, 대략 n * k * 4B = 100 * 10,000 * 4B = 10^6 * 4B = 4MB이다.

문제 제한은 4MB인데, 실제로는 엄밀히는 (n+1) * (k+1)이고, 함수 호출 스택, 지역변수 등을 고려했을때는 메모리 제한이 너무 타이트하다.

 

따라서, 메모리를 아끼기 위해서는 1차원 배열을 이용해야 된다. 정확히는 현재 새로운 동전(x번째)을 추가했을 때, 이전(x-1번째)까지의 동전을 고려한 경우의 수가 사용되므로 1차원 배열 2개(이전까지 동전 고려 + 새로운 동전 고려)가 필요 할 것이다.

1차원 배열 2개에 필요한 공간복잡도는 약 2 * k * 4B = 2 * 10,000 * 4B = 80KB이므로 문제 제한인 4MB에 충분하다.

 

1차원 DP 풀이의 시간복잡도

새로운 동전을 고려했을 때의 DP배열을 모두 채운 후에는, 다시 이전까지의 동전을 고려한 DP배열에 옮겨줘야 한다. 즉, 앞에서 구한 DP풀이의 시간복잡도에 추가적으로 배열을 복사하는 데 소요되는 시간이 추가될 것이다.

대략적으로 길이가 k인 배열을 총 n번 복사하게 되므로, n * k = 100 * 10,000 = 10^6이 추가적으로 필요하다.

따라서, 총 시간복잡도는 10^6 + 10^6 = 2* 10^6이므로, 문제 제한인 1초에 충분하다. 

 

코드

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[] coins = new int[n+1];
		for(int i=1; i<=n; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		
		int[] dp = new int[k+1]; // 이전까지의 동전을 고려했을 때의 dp배열
		dp[0] = 1; // 아무 동전 없이 0원을 만드는 경우의 수는 1개 (아무 동전도 사용 x)
		
		// 고려하는 동전을 1개씩 늘려감
		for(int i=1; i<=n; i++) {
			int coin = coins[i]; // 현재 추가된 동전
			int[] newDp = new int[k+1]; // 새로운 동전까지 고려했을 때의 dp배열
			for(int j=0; j<=k; j++) {
				// 추가된 동전 사용 x
				newDp[j] = dp[j];
				
				// 추가된 동전 사용 o(무조건 1개는 포함)
				if(j-coin >= 0) {
					newDp[j] += newDp[j-coin];
				}
			}
			// 다시 이전까지의 동전을 고려했을 때의 dp배열에 복사
			dp = Arrays.copyOf(newDp, k+1);
		}
		
		System.out.println(dp[k]);
	}
}