[다이나믹] HackerRank# The Coin Change Problem

[ye-yo]

⚠️ 나의 풀이

arr[j-c[i]까지 접근했으나 더이상 풀이를 진행해나가지 못함

❗️ 오답 원인 분석

🔑 풀이 핵심

참고 : https://www.geeksforgeeks.org/coin-change-dp-7/

  dp[0] = 1; //1을 할당해줘야 경우의 수 1씩 추가 가능
  for(int i=0; i<c.size(); i++){
      for(int j= c[i]; j<=n; j++){// c[i]부터 시작하는 이유는 c[i] 이하의 수 주어진 동전이 없어서 동전 합을 만들 수 없음
          dp[j] += dp[j-c[i]];         
      }
  }     

예를 들어 j가 10이고 동전 1,2,5를 가지고 있다면 경우의 수는 다음과 같다.

• 1원 + dp[9]
• 2원 + dp[8]
• 5원 + dp[5]

이 개념을 위의 코드에 대입하면 다음과 같이 계산해나가는 것

  for(int i=0; i<c.size(); i++){
      for(int j= c[i]; j<=n; j++){
            //dp[1] += dp[1-1원], dp[2] += d[2-1원], dp[3] += d[3-1원]....
      }     
}