shoeskwang   3년 전

안녕하세요.

2293 동전 문제 DP로 풀어보고 싶어서


for(int i=1;i<=n;i++){
   for(int j=0;j<=k;j++){
    if(A[i]<=j){
     dp[j]+= dp[j-A[i]];
    }
   }
  }
  
  System.out.println(dp[k]);


이런 소스를 구해서 돌려봤는데요.


처음부터 차근차근히 설명이 나와있는 곳이 없어서 잘 이해가 가지 않습니다.


분할정복을 사용한다는거도 같고..

동적계획법에 대해서 잘 모르는데


소스를 돌려봐서 전체 동전 갯수를 증가시키면서? 하는거 같던데..


dp[j]+= dp[j-A[i]]; 라는 식이 나오기까지의 과정을 알 수 있을까요?


기초적인것부터 알수 있는 사이트나 설명 해주시면 정말 감사하겠습니다.


danbi2990   3년 전

먼저 1원만 써서 만들수 있는 경우의 수를 찾습니다. 1원으로 0~10원을 만드는 경우는 각각 한 가지 밖에 없죠.

A0 = 1, A1 = 1, A2 = 1, A3 = 1, A4 = 1, A5 = 1, A6 = 1, ..., A10 = 1

그 다음 2원이 추가됐을 때 경우를 셉니다.

A0 = 1, A1 = 1, A2 = 2, A3 = 2, A4 = 3, A5 = 3, A6 = 4, ..., A10 = ?

규칙을 찾으셨나요?

2원이 추가됐을 때 An = An + An-2 입니다.


예를 들어 A2를 구성하는 경우는 1+1 (1로만 구성된 A2)과 0+2 (A0에 2를 더한 경우, 즉 적어도 2원을 한 번 쓴 경우) 두 가지 입니다.

A3을 구성하는 경우: 2가지

A3: 1+1+1 (1원으로만 구성)

A1+2: 1+2 (적어도 2원을 한 번 쓴 경우)


A4을 구성하는 경우: 3가지

A4: 1+1+1+1

A2+2: 1+1+2, 0+2+2


5원이 추가된 경우도 마찬가지로 진행됩니다.

tddhot2   3년 전

danbi2990 


적어주신 설명 너무 구체적이고 자세해서 아주 잘 참고가 됩니다!

혹시, 저런 규칙을 알아내는 과정 또한 아무것도 없는 상태에서 알아내는 것인지,

아니면 어떠한 틀이나 공식에따라 저런 점화식 공식을 발견해낼 수 있는 것인지에

대해서 궁금합니다!!!

댓글을 작성하려면 로그인해야 합니다.