[6주차_수요일] 동전

[icegosimperson]

• 사이트 : 백준(BOJ)
• 문제: 동전
• 번호: 9084

  🤔 시간복잡도 고려사항
  💡 풀이 아이디어

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP
• 시간복잡도: 1 ≤ 동전 수 ≤ 20, 1 ≤ 동전 금액 ≤ 10000 조합으로 풀 경우 10000C20 으로 연산불가 DP 로 풀 경우 O(동전수*동전금액) 으로 10^5 연산 가능

💡 풀이 아이디어

• 목표 동전(M) 을 만들기 위한 경우의 수 구하기
  • dp[M] = 경우의 수
• 현재 코인으로 만들 수 있는 경우의 수는 이미 계산된 [M-현재코인]의 경우의 수와 동일하다
• M 을 만들기 위한 전체 경우의 수는 각각의 코인들로 만들 수 있는 경우의 수를 모두 합한 것이다
  • 따라서 각 코인의 경우의 수를 누적하여 계산한다.

메모리제이션 테이블을 만들 때 규칙성을 찾기 위해 어떻게 이미 계산된 값을 재사용할지 생각하기....................... 참고 블로그

[baexxbin]

🤔 시간복잡도 고려사항

• 동전의 가지 수 N(1 ≤ N ≤ 20)
• 1 <= 각 금액 <= 10000
• 만들어야 할 금액 M(1 ≤ M ≤ 10000)
• O(N*M) →O(10^5)

💡 풀이 아이디어

• dp[i] = k, 동전i로 만들 수 있는 경우의 수 k
  • 금액(j)-현재 동전(i) >=0 이면 dp[i]+1로 경우의 수 누적하기

• 처음 아이디어 (틀림)

  // 초기화
  int[] dp = new int[M + 1];
  Arrays.fill(dp, Integer.MIN_VALUE);
  dp[0] = 0;
  
  // 점화식
  for (int c : coin) {
      for (int i = c; i <= M; i++) {
          if (dp[i-c] != Integer.MIN_VALUE){
              dp[i] = dp[i] == Integer.MIN_VALUE ? 1 : dp[i] + 1;
          }
      }
  }

  • 만들 수 없는 경우는 INF로 설정하고 만들 수 있을 때만 +1씩 추가해주려했는데 실패
  • 0일경우도, 0원 만들경우 1이므로 dp[0] =1로 설정하기

• 수정 버전

  // 초기화
  int[] dp = new int[M + 1];
  dp[0] = 1;
  
  // 점화식
  for (int c : coin) {
        for (int i = c; i <= M; i++) {
            dp[i] += dp[i - c];
        }
    }

• 초기화는 INF가 아닌 0으로 초기화, dp[0]=1
• dp[i - c]에서 어짜피 못만드는 값이면 0이기에 더해줘도 변화 없음(이전에 INF이용하려한 부분)

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 동전의 가지 수 <= 20이고, 동전의 개수 제한이 없기 때문에 완전 탐색으로 모든 경우를 구하는 경우는 불가능하다고 생각함
• DP를 사용한다면 O(N×M)에 해결 가능

💡 풀이 아이디어

• int[] dp: M원을 만들 때의 경우의 수
• dp[0]: 0원을 만드는 경우는 모든 동전을 사용하지 않는 경우이므로 1로 초기화
• 현재 경우의 수 = 현재 경우의 수 + dp[i - 현재 동전]으로 구해줌

  for(int c: coin) {
    for(int i = 0; i < dp.length; i++) {
        if(i - c < 0) continue;
        dp[i] += dp[i - c];
    }
  }

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : T N M = O(N) 가능

💡 풀이 아이디어

• 주어진 금액을 만드는 모든 방법의 수
• dp로 푼 이유 : 각 동전이 주어졌을 때 금액을 만드는 다양한 방법을 모두 계산

          for(int i=0; i<N; i++){
              for(int j=coins[i]; j<M+1; j++){
                  dp[j] += dp[j - coins[i]]; // 해당 동전 사용할 수 있는 금액 + 
          }

[yeongleej]

🤔 시간복잡도 고려사항

• T ≤ 10
• N ≤ 20
• M ≤ 10000

=> 테스트케이스 T 동전 가지수 N 만들금액 M == 2,000,000 : 선형탐색으로 생각해보기

💡 풀이 아이디어

• 동전의 각 금액이 오름차순으로 정렬되어 있으므로 1~N번쨰 동전으로 j 비용을 만들 수 있는 경우의 수를 차례대로 구함
• dp[0] = 1로 초기화 : 어떤 동전으로도 0원을 만들 수 있는 경우의 수는 1 => 즉, 0원을 만드는 경우의수 1개
• dp[j] : 비용 i를 만들 수 있는 경우의 수
  • dp[j] = dp[j] + dp[j-coin[i]];
  • j 비용을 만들 수 있는 경우의 수 = (i-1)번째 동전으로까지 만들수 있는 경우의수 + 현재 i번쨰 동전을 추가해서 만들 수 있는 경우의 수

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ T ≤ 10, 1 ≤ N ≤ 20, 1 ≤ M ≤ 10000 → T x N x M = 2 x 10^6 이므로 충분히 가능!

💡 풀이 아이디어

• 특정 금액을 만드는 조합 수의 총 합을 구하는 문제 → DP , knapsack
• 특정 금액을 만들기 위해서는 사용하려는 동전과 이전에 만들어 둔 값을 이용해서 조합의 수를 계산

  // knapsack - 중복 사용 가능
  for (int coin : coins)
      // 현재 동전으로 만들 수 있는 조합의 수 계산
      for (int i = coin; i < m + 1; i++)
          dp[i] += dp[i - coin];