[백준(Baekjoon)][자바(java)] 2293 : 동전 1 / 동적 계획법 2

 

www.acmicpc.net/problem/2293

2293번: 동전 1

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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() ), 
		    k = Integer.parseInt( st.nextToken() );
		int c[] = new int[n+1], i, j;
		for( i = 1; i <= n; i++ )
			c[i] = Integer.parseInt( br.readLine() );
		br.close();
		
		int dp[][] = new int[n+1][k+1];
		dp[0][0] = 1;
		for( i = 1; i <= n; i++ ) {
			for( j = 0; j <= k; j++ ) {
				dp[i][j] = dp[i-1][j];
				if( c[i] <= j )
					dp[i][j] += dp[i][j-c[i]];
			}
		}
		
		System.out.println( dp[n][k] );

	}
} 

 

* 배낭( 냅색 ) 문제의 응용 

( 백준 12865 - 평범한 배낭  hyunjiishailey.tistory.com/132 )

 

☞  n : 동전의 종류 가짓수

☞  k : 총 가치의 합

i번째 코인까지 사용하여 가치의 합이 j가 되는 경우의 수를 담을 2차원 int dp[ n+1 ][ k+1 ] 배열 생성  ( dp[0][0] = 1 )

dp[ i ][ j ]에서 i는 i번째 요소( c[ i ] )까지 포함한다는 뜻이고 d[ i ][ j ]는 가치의 합이 j가 되는 경우의 수를 말함

☞  c[ i ] : i번째 코인의 가치 ( k_i )

☞  dp[ i ][ j ] : i번째 코인까지 사용하여 j를 만들 수 있는 경우의 수

이중 루프를 돌며 c[ i ]와 j를 비교한다  ( 1 <= i <= n ) ( 0 <= j <= k )

c[ i ]가 j보다 크면 dp[ i ][ j ] 는 dp[ i-1 ][ j ] 와 같다

c[ i ]가 j보다 작거나 같으면 dp[ i ][ j ]는  dp[ i-1 ][ j ] + dp[ i ][ j-c[i] ] 이다