백준 2293번 동전 1 JAVA

링크텍스트

설명

1원짜리로면 dp채우면
dp[0]=1, dp[1]=1
dp[2]=1, dp[3]=1
dp[4]=1, dp[5]=1
dp[6]=1, dp[7]=1
dp[8]=1 ,dp[9]=1
dp[10]=1

2원짜리로 채우면
dp[2] += dp[0] → dp[2] = 2
dp[3] += dp[1] → dp[3] = 2
dp[4] += dp[2] → dp[4] = 3
dp[5] += dp[3] → dp[5] = 3
dp[6] += dp[4] → dp[6] = 4
dp[7] += dp[5] → dp[7] = 4
dp[8] += dp[6] → dp[8] = 5
dp[9] += dp[7] → dp[9] = 5
dp[10] += dp[8] → dp[10] = 6

5원짜리로 채우면
dp[5] += dp[0] → dp[5] = 4
dp[6] += dp[1] → dp[6] = 5
dp[7] += dp[2] → dp[7] = 6
dp[8] += dp[3] → dp[8] = 7
dp[9] += dp[4] → dp[9] = 8
dp[10] += dp[5] → dp[10] = 10

순서를 고려하지않기때문에 첫번째 for문에서 동전을 고른 후 k까지의 금액을 확인한다. 만약
순서가 다를경우 다른 경우로 취급할거면 첫번째 for문을 k까지의 금액, 두번째 for문에서 동전 고르면 된다.
시간복잡도: O(N*K), 공간복잡도: O(N+K)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.util.*;
import java.io.*;

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 [] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        int [] dp = new int[k+1];
        dp[0] = 1;

        for(int i=0;i<n;i++){
            int coin = arr[i];
            for(int j=coin;j<=k;j++){
                dp[j]+=dp[j-coin];
            }
        }

        System.out.println(dp[k]);
    } 
}

for (int j = 1; j <= k; j++) {         // 1 ~ k까지 금액에 대해
    for (int i = 0; i < n; i++) {      // 모든 동전을 순서대로 확인
        int coin = arr[i];
        if (j >= coin) {
            dp[j] += dp[j - coin];
        }
    }
}