백준 동전1(복습)

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

2293번: 동전 1

백준 동전1문제 오답노트를 해야겠네요. dp 유명한공식문제라 기억해야하겠습니다.

 

package test01;
import java.util.*;

import java.lang.*;
import java.io.*;
public class Main {
	
	public static void main(String[] args) throws Exception {
		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		int k=scan.nextInt();
		int coin[]=new int[n];
		for(int i=0;i<n;i++) {
			int tmp=scan.nextInt();
			coin[i]=tmp;
		
		}
		int dp[]=new int[k+1];
		//1~10dp
		//초기값
		dp[0]=1;

		for(int i=0;i<n;i++) {
			//1,2,5 coin
			for(int j=coin[i];j<=k;j++) {
				dp[j]=dp[j]+dp[j-coin[i]];
			}
		}
		
		System.out.println(dp[k]);
		
	}
	
}

오답노트:

동전 coin = 1,2,5

for(int i=0;i<n;i++) 
{
		int tmp=scan.nextInt();
		coin[i]=tmp;
 }

경우의 수 저장할 공간

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

 

초기값 설정 및 경우의수 누적합

 

dp[0]=1;

for(int i=0;i<n;i++) {
//1,2,5 coin
	for(int j=coin[i];j<=k;j++) {
		dp[j]=dp[j]+dp[j-coin[i]];
	}
}

먼저 i=0인경우 coin[0]니까 1 원이겠죠

그렇다면 dp에는 

dp[j]=dp[j]+dp[j-coin[i]];

dp[현재누적값 j ]=dp[과거누적값 j]+ dp[ 현재 j - 현재 코인의 값 ]

1 원의 누적데이터 

그림을 보시면 1원의 1원이 되기 위한 경우의수 1이죠 나머지 마찬가지로 10원까지 전부 1일겁니다.

i=1인경우coin[1]니까 2 원이겠죠

그렇다면 dp는 마찬가지로 계산하면 

dp[j]=dp[j]+dp[j-coin[i]]; 

계산 먼저 하면 dp[2]=dp[2]+dp[ 2-2 ]; =>dp[2]=dp[2]+dp[0] => 2=1+1; 가 되겠죠 

왜냐히먄 2가 되는 경우의수는 기존의 1coin의 경우의수 1가지, 그리고 2가 되는 한가지겠죠 

이런식으로 증가하겠죠

 

다음은 

i=2인경우 coin[2]니까 5 원이겠죠

 

기발한 아이디어 라고할까요 저는 노력하는 범재라 이런생각까지 오는게 정말 쉽지않네요.. ㅠㅠ 내공이 부족하다고 여러번 느끼네요